记录编号	542309	评测结果	AAAAAAAAAAAAAAAAAAAE
题目名称	[NOIP 2016]天天爱跑步	最终得分	95
用户昵称	Hale	是否通过	未通过
代码语言	C++	运行时间	1.124 s
提交时间	2019-09-23 13:55:19	内存使用	53.71 MiB

#include<bits/stdc++.h>
#define I inline
using namespace std;
const int N=3e5+7;
int head[N],dep[N],size[N],fa[N],top[N],w[N],cnt2[N],cnt1[N],son[N];
int s[N],ans[N];
int m,n,k,mx,tot;
vector<int> q1[N],q2[N],q3[N];
I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
I void write(int x)
{
	if (x<0) {putchar('-'); x=-x;}
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
struct edge
{
	int nx,to;
} e[N];
struct line
{
	int fro,to,dis,lca;
}p[N];
void add_edge(int a,int b)
{
	tot++;e[tot].nx=head[a];e[tot].to=b;head[a]=tot;
}
void dfs1(int x,int ff,int deep)
{
    dep[x]=deep;fa[x]=ff;size[x]=1;
    for (int i=head[x];i;i=e[i].nx)
    {
        int y=e[i].to;
        if (y==ff) continue;
        dfs1(y,x,deep+1);
        size[x]+=size[y];
        if (size[y]>size[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int topfa)
{
    top[x]=topfa;
    if (!son[x]) return;
    dfs2(son[x],topfa);
    for (int i=head[x];i;i=e[i].nx)
    {
        int y=e[i].to;
        if (y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
int get_lca(int x,int y)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) return y;
    else return x;
}
void dfs(int x)
{
	int now=w[x]+dep[x],cun;if (now<=mx) cun=cnt1[now];
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==fa[x]) continue;
		dfs(y);
	}
	cnt1[dep[x]]+=s[x];if (now<=mx) ans[x]=cnt1[now]-cun;
	for (int i=0;i<q1[x].size();i++) cnt1[dep[q1[x][i]]]--;
}
void dfss(int x)
{
	int now=dep[x]-w[x]+n,cum=cnt2[now];
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==fa[x]) continue;
		dfss(y);
	}
	for (int i=0;i<q2[x].size();i++) cnt2[q2[x][i]+n]++;
	ans[x]+=cnt2[now]-cum;
	for (int i=0;i<q3[x].size();i++) --cnt2[q3[x][i]+n];
}
int main()
{
	freopen("runninga.in","r",stdin);
	freopen("runninga.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<n;i++)
	{
		int x=read(),y=read();
		add_edge(x,y);add_edge(y,x);
	}
	for (int i=1;i<=n;i++) w[i]=read();
	for (int i=1;i<=m;i++) p[i].fro=read(),p[i].to=read();
	dfs1(1,0,1);dfs2(1,0);for (int i=1;i<=n;i++) mx=max(mx,dep[i]);
	for (int i=1;i<=m;i++)
	{
		p[i].lca=get_lca(p[i].fro,p[i].to);
		s[p[i].fro]++;
		p[i].dis=dep[p[i].fro]+dep[p[i].to]-dep[p[i].lca]*2;
		q1[p[i].lca].push_back(p[i].fro);
	}
	dfs(1);
	for (int i=1;i<=m;i++)
	{
		q2[p[i].to].push_back(dep[p[i].to]-p[i].dis);
		q3[p[i].lca].push_back(dep[p[i].to]-p[i].dis);
	}
	dfss(1);
	for (int i=1;i<=m;i++) if (dep[p[i].fro]-dep[p[i].lca]==w[p[i].lca]) ans[p[i].lca]--;
	for (int i=1;i<=n;i++) write(ans[i]),putchar(' ');
	return 0;
}