记录编号	356583	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	3.231 s
提交时间	2016-12-02 00:21:54	内存使用	30.09 MiB

#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>
#include <cstring>
#define file(x) "runninga." #x
using std::min;
using std::max;
namespace I{
	const int L  = 1 << 15;
	char buf[L], *s, *t;
	inline char gc() {
		if (s == t) t = (s=buf) + fread(buf, 1, L, stdin);
		if (s == t) return EOF;
		return *s++;
	}
	inline int gi() {
		int s = 0, ch = gc();
		while (!isdigit(ch)) ch = gc();
		while (isdigit(ch)) s = s*10 + ch - '0', ch = gc();
		return s;
	}
}using I::gi;
const int N = 3e5 + 10;
int n, m, w[N], s[N], t[N], dfn[N], dfsclk, fa[N], son[N], top[N], sz[N], dep[N], ver[N], anc[N], ret[N];
std::vector<int> in[N], out[N];
int esz, hed[N], nxt[N << 1], st[N << 1];
int dfs1(int u) {
	sz[u] = 1;
	for (int i = hed[u], v; i; i = nxt[i]) if (fa[u] != (v = st[i])) {
		fa[v] = u;
		dep[v] = dep[u] + 1;
		sz[u] += dfs1(v);
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
	return sz[u];
}
void dfs2(int u, int now) {
	ver[dfn[u] = ++dfsclk] = u;
	top[u] = now;
	if (son[u]) dfs2(son[u], now);
	for (int i = hed[u], v; i; i = nxt[i]) if (fa[u] != (v = st[i]) && v != son[u]) {
		dfs2(v, v);
	}
}
inline bool cmp(int a, int b) {return dep[a] < dep[b];}
inline int lca(int a, int b) {
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]]) std::swap(a, b);
		a = fa[top[a]];
	}
	return min(a, b, cmp);
}
int cnt[N*3];
void cha(int l, int r, int v, bool ty) {
	if (l > r) return;
	if (ty) in[r].push_back(v), out[l - 1].push_back(v);
	else in[l].push_back(v), out[r + 1].push_back(v);
}
void modi(int a, int b, int t, bool ty) {
	if (t < 0) t += n << 1;
	while (top[a] != top[b]) {
		if (dep[top[a]] < dep[top[b]]) std::swap(a, b);
		cha(dfn[top[a]], dfn[a], t, ty);
		a = fa[top[a]];
	}
	if (dep[a] < dep[b]) std::swap(a, b);
	if (ty) cha(dfn[b] + 1, dfn[a], t, ty);
	else cha(dfn[b], dfn[a], t, ty);
}
void sa(int u, int v) {
	st[++esz] = v;
	nxt[esz] = hed[u];
	hed[u] = esz;
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	n = gi(), m = gi();
	for (int i = 1; i < n; i++) {
		int u = gi(), v = gi();
		sa(u, v), sa(v, u);
	}
	for (int i = 1; i <= n; i++) w[i] = gi();
	dfs1(1), dfs2(1, 1);
	for (int i = 1; i <= m; i++) s[i] = gi(), t[i] = gi(), anc[i] = lca(s[i], t[i]);
	for (int i = 1; i <= m; i++) {
		//if (dep[s[i]] < dep[anc[i]]) modi(s[i], anc[i], dep[s[i]], 0);
		modi(t[i], anc[i], dep[anc[i]] - (dep[s[i]] - dep[anc[i]]), 0);
	}
	for (int i = 1; i <= n + 1; i++) {
		int u = ver[i];
		for (int j = 0; j < in[i].size(); j++) ++cnt[in[i][j]];
		for (int j = 0; j < out[i].size(); j++) --cnt[out[i][j]];
		if (dep[u] - w[u] >= 0) ret[u] += cnt[dep[u] - w[u]];
		else if (dep[u] - w[u] + (n << 1) >= 0) ret[u] += cnt[dep[u] - w[u] + (n << 1)];
	}
	for (int i = 1; i <= n + 1; i++) in[i].clear(), out[i].clear();
	for (int i = 1; i <= m; i++) {
	 modi(s[i], anc[i], dep[s[i]], 1);
	}
	for (int i = n; i; i--) {
		int u = ver[i];
		for (int j = 0; j < in[i].size(); j++) ++cnt[in[i][j]];
		for (int j = 0; j < out[i].size(); j++) --cnt[out[i][j]];
		if (dep[u] + w[u] <= n) ret[u] += cnt[dep[u] + w[u]];
	}
	for (int i = 1; i <= n; i++) printf("%d ", ret[i]);
}