记录编号	437502	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	2.294 s
提交时间	2017-08-14 11:00:21	内存使用	36.28 MiB

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<iostream>
#define N 300000
using namespace std;
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
	return sum*f;
}
int n,m,adj[N],f[N],vis[N],dep[N],anc[N],ans[N];
int tim[N],A[N],sum[N],up[N*2],down[N*2];
int e,e1,e2,e3,e4;
int adj1[N*2],adj2[N*2],adj3[N*2],head[N];
struct Q{int v,next,id;}q[N*2];
struct road{int v,next;}lu[N*2],lu1[N*2],lu2[N*2],lu3[N*2];
void add(int u,int v){lu[++e].v=v;lu[e].next=adj[u];adj[u]=e;}
void add1(int u,int v){lu1[++e1].v=v;lu1[e1].next=adj1[u];adj1[u]=e1;}
void add2(int u,int v){lu2[++e2].v=v;lu2[e2].next=adj2[u];adj2[u]=e2;}
void add3(int u,int v){lu3[++e3].v=v;lu3[e3].next=adj3[u];adj3[u]=e3;}
void add_q(int u,int v,int id){q[e4].v=v;q[e4].id=id;q[e4].next=head[u];head[u]=e4++;}
int find(int x){return f[x]==x? x:f[x]=find(f[x]);}
void hb(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy)f[fx]=fy;}
void dfs1(int x,int fa)
{
	dep[x]=dep[fa]+1;anc[x]=x;vis[x]=1;
	for(int i=adj[x];i;i=lu[i].next)
	{
		int to=lu[i].v;
		if(vis[to])continue;
		dfs1(to,x);
		hb(x,to);anc[find(x)]=x;
	}
	for(int i=head[x];i!=-1;i=q[i].next)
	{
		int to=q[i].v;
		if(vis[to])ans[q[i].id]=anc[find(to)];
	}
}
void dfs2(int x,int y)
{
	int t1=up[dep[x]+tim[x]],t2=down[dep[x]-tim[x]+N];
	up[dep[x]]+=A[x];
	for(int i=adj1[x];i;i=lu1[i].next)
	   ++down[lu1[i].v+N];
	for(int i=adj[x];i;i=lu[i].next)
	   if(lu[i].v!=y)dfs2(lu[i].v,x);
	sum[x]=up[dep[x]+tim[x]]+down[dep[x]-tim[x]+N]-t1-t2;
	for(int i=adj2[x];i;i=lu2[i].next)
	{
		int to=lu2[i].v;
		up[to]--;
		if(to==dep[x]+tim[x])
		    sum[x]--;
	}
	for(int i=adj3[x];i;i=lu3[i].next)
	     down[lu3[i].v+N]--;
}
int main()
{
	freopen("runninga.in","r",stdin);
	freopen("runninga.out","w",stdout);
	int __size__=64<<20; 
    char *__p__=(char*)malloc(__size__)+__size__;  
    __asm__("movl %0, %%esp\n"::"r"(__p__));  
	n=read();m=read();int x,y,a,b;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<n;i++)x=read(),y=read(),add(x,y),add(y,x);
	for(int i=1;i<=n;i++)tim[i]=read();
	for(int i=0;i<m;i++)x=read(),y=read(),add_q(x,y,i),add_q(y,x,i);
	dfs1(1,0);
	for(int i=0;i<m;i++)
	{
		x=q[i<<1].v,y=q[i<<1|1].v;
		a=dep[x]+dep[y]-dep[ans[i]]*2;b=dep[x]-a;
		++A[y];add1(x,b);add2(ans[i],dep[y]);add3(ans[i],b);
	}
	dfs2(1,0);
	for(int i=1;i<=n;i++)printf("%d ",sum[i]);
}