记录编号	513375	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	3.339 s
提交时间	2018-10-10 21:45:10	内存使用	47.33 MiB

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) x&-x;
using namespace std;
const int N = 3e5+7;
map<int, int> book[2];
int w[N], ans[N], dep[N], anc[N][22], checker[N];
vector<int> vec[N], del[N][2], tag[N][2];
char gc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2) ? EOF : *p1++;
}
int qr()
{
    char ch = gc();
    int f = 1, sum = 0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f = -1;
        }
        ch = gc();
    }
    while(ch>='0'&&ch<='9')
    {
        sum = sum*10+ch-'0';
        ch = gc();
    }
    return sum*f;
}
void dfs(int x, int fa)
{
    anc[x][0] = fa;
    dep[x] = dep[fa]+1;
    for(int i = 1; i <= 18; i++)
    {
        anc[x][i] = anc[anc[x][i-1]][i-1];
    }
    for(int i = 0; i < vec[x].size(); i++)
    {
        int y = vec[x][i];
        if(y!=fa)
        {
            dfs(y, x);
        }
    }
    return;
}
int lca(int x, int y)
{
    if(dep[x]<dep[y])
    {
        swap(x, y);
    }
    for(int i = 18; i >= 0; i--)
    {
        if(dep[anc[x][i]]>=dep[y])
        {
            x = anc[x][i];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(int i = 18; i >= 0; i--)
    {
        if(anc[x][i]!=anc[y][i])
        {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0] == 0 ? 1 : anc[x][0];
}
void calc(int x)
{
    int d1 = dep[x]-w[x], d2 = dep[x]+w[x];
    int last = book[0][d2]+book[1][d1];
    for(int i = 0; i < vec[x].size(); i++)
    {
        int y = vec[x][i];
        if(y!=anc[x][0])
        {
            calc(y);
        }
    }
    for(int j = 0; j < 2; j++)
    {
        for(vector<int>::iterator it = tag[x][j].begin(); it != tag[x][j].end(); it++)
        {
            book[j][*it]++;
        }
        for(vector<int>::iterator it = del[x][j].begin(); it != del[x][j].end(); it++)
        {
            book[j][*it]--;
        }
    }
    ans[x] = book[0][d2]+book[1][d1]-last;
    return;
}
int main()
{
    int __size__=128<<20;
    char*__p__=(char*)malloc(__size__)+ __size__;
    __asm__("movl %0, %%esp\n"::"r"(__p__));
    //freopen("test.in", "r", stdin);
    freopen("runninga.in","r",stdin);
	freopen("runninga.out","w",stdout);
    int n = qr(), m = qr();
    for(int i = 2; i <= n; i++)
    {
        int u = qr(), v = qr();
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++)
    {
        w[i] = qr();
    }
    for(int i = 1; i <= m; i++)
    {
        int s = qr(), t = qr();
        int LCA = lca(s, t);
        checker[s]++;
        tag[s][0].push_back(dep[s]);
        del[anc[LCA][0]][0].push_back(dep[s]);
        tag[t][1].push_back(2*dep[LCA]-dep[s]);
        del[LCA][1].push_back(2*dep[LCA]-dep[s]);
    }
    calc(1);
    for(int i = 1; i <= n; i++)
    {
        printf("%d ", ans[i]);
    }
    puts("");
    return 0;
}