记录编号	566442	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.631 s
提交时间	2021-11-08 19:57:11	内存使用	91.57 MiB

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 500005;
int n,m;
int W[maxn];
int d[maxn],f[maxn][20],lg[maxn];
int ans[maxn];
int head[maxn],ver[maxn << 1],nxt[maxn << 1];
int c[maxn << 1];
int cnt = 0;
vector<int> g[maxn];
vector<int> num[maxn];
void LCApre(int u,int d) {
	for(int k = 1;k <= lg[d];++ k)
		f[u][k] = f[f[u][k - 1]][k - 1];
	return ;
}
int LCA(int u,int v) {
	if(d[u] < d[v])swap(u , v);
	for(int k = lg[d[u]];~ k;-- k) {
		if(d[u] - (1 << k) >= d[v]) {
			u = f[u][k];
		}
		if(u == v)return u;
	}
	if(u == v)return u;
	for(int k = lg[d[u]];~ k;-- k) {
		if(f[u][k] != f[v][k]) {
			u = f[u][k];
			v = f[v][k];
		}
	}
	return f[u][0];
}
void add(int u,int v) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	return ;
}
void dfs(int u,int fa) {
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(v == fa)continue ;
		f[v][0] = u;
		d[v] = d[u] + 1;
		LCApre(v , d[v]);
		dfs(v , u);
	}
	return ;
}
void calc(int u,int fa) {
	int tot  = c[W[u] + d[u]];
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(v == fa)continue ;
		calc(v , u);
	}
	for(int i = 0;i < g[u].size();++ i) {
		c[g[u][i]] += num[u][i];
	}
	ans[u] += c[W[u] + d[u]] - tot;
	return ;
}
void CALC(int u,int fa) {
	int tot  = c[W[u] - d[u]];
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i];
		if(v == fa)continue ;
		CALC(v , u);
	}                                        
	for(int i = 0;i < g[u].size();++ i) {
		c[g[u][i]] += num[u][i];
	}
	ans[u] += c[W[u] - d[u]] - tot;
	return ;
}
int s[maxn],t[maxn];
int main() {
	freopen("runninga.in","r",stdin);
	freopen("runninga.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 2;i <= n;++ i) {
		int u,v;
		scanf("%d%d",&u,&v);
		add(u , v);
		add(v , u);
		lg[i] = lg[i >> 1] + 1;
	}
	dfs(1 , 0);
	for(int i = 1;i <= n;++ i) {
		scanf("%d",&W[i]);
	}
	for(int i = 1;i <= m;++ i) {
		scanf("%d%d",&s[i],&t[i]);
		int p = LCA(s[i] , t[i]);
		g[s[i]].push_back(d[s[i]]);
		num[s[i]].push_back(1);
		if(f[p][0])g[f[p][0]].push_back(d[s[i]]),num[f[p][0]].push_back(-1);
	}
	calc(1 , 0);
	for(int i = 0;i <= n;++ i)g[i].clear(),num[i].clear();
	for(int i = 1;i <= m;++ i) {
		int p = LCA(s[i] , t[i]);
		int dist = d[s[i]] - 2 * d[p];
		g[t[i]].push_back(dist);
		num[t[i]].push_back(1);
		g[p].push_back(dist);
		num[p].push_back(-1);
	}
	CALC(1 , 0);
	for(int i = 1;i <= n;++ i)printf("%d ",ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}