记录编号	509070	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	1.395 s
提交时间	2018-09-12 22:05:03	内存使用	49.17 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 300005
#define maxx 600010
#define MA 300000
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read(){   
    char c=getchar();int x=0,y=1;
    while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}
int n,m,ans[maxn],fans[maxn],dp[maxn],ance[maxn],f[maxn],hea[maxn],nhea[maxn],num,nnum,num1,num2,num3,A[maxn];
int hea1[maxx],hea2[maxx],hea3[maxx],tim[maxn],dn[maxx],upp[maxx];
bool ok[maxn];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void unionn(int x,int y){int a=find(x),b=find(y);if(a!=b) f[a]=b;}
struct road{int en,nex;}ro[maxx],ro1[maxx],ro2[maxx],ro3[maxx];
struct query{int en,nex,id;}qu[maxx];
inline void addq(int x,int y,int z){	
    qu[nnum].en=y;qu[nnum].id=z;qu[nnum].nex=nhea[x];nhea[x]=nnum++;
	qu[nnum].en=x;qu[nnum].id=z;qu[nnum].nex=nhea[y];nhea[y]=nnum++;
}
inline void add(int x,int y){ro[num].en=y;ro[num].nex=hea[x];hea[x]=num++;}
inline void add1(int x,int y){ro1[num1].en=y;ro1[num1].nex=hea1[x];hea1[x]=num1++;}
inline void add2(int x,int y){ro2[num2].en=y;ro2[num2].nex=hea2[x];hea2[x]=num2++;}
inline void add3(int x,int y){ro3[num3].en=y;ro3[num3].nex=hea3[x];hea3[x]=num3++;}
void lca(int x,int y){	
    ance[x]=x;ok[x]=1;dp[x]=dp[y]+1;
	for(int i=hea[x];i!=-1;i=ro[i].nex){	
	    int v=ro[i].en;if(ok[v]) continue;
		lca(v,x);unionn(x,v);ance[find(x)]=x;
	}
	for(int i=nhea[x];i!=-1;i=qu[i].nex){	
	    int v=qu[i].en;
		if(ok[v]) ans[qu[i].id]=ance[find(v)];
	}
}
void dfs(int x,int y){	int t1=upp[dp[x]+tim[x]],t2=dn[dp[x]-tim[x]+MA];upp[dp[x]]+=A[x];
	for(int i=hea1[x];i!=-1;i=ro1[i].nex) ++dn[ro1[i].en+MA];
	for(int i=hea[x];i!=-1;i=ro[i].nex) if(ro[i].en!=y) dfs(ro[i].en,x);
	fans[x]=upp[dp[x]+tim[x]]+dn[dp[x]-tim[x]+MA]-t1-t2;
	for(int i=hea2[x];i!=-1;i=ro2[i].nex){int v=ro2[i].en;--upp[v];if(v==dp[x]+tim[x]) --fans[x];}
	for(int i=hea3[x];i!=-1;i=ro3[i].nex) --dn[ro3[i].en+MA];
}
void init(){	
    mem(hea,-1);mem(nhea,-1);mem(hea1,-1);mem(hea2,-1);mem(hea3,-1);
	for(int i=1;i<=n;++i) f[i]=i;
}
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();
	init();int x,y;
	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(),addq(x,y,i);
	lca(1,0);int fr,to,tmp1,tmp2;
	for(int i=0;i<m;++i){	
	to=qu[i<<1].en;fr=qu[i<<1|1].en;
		tmp1=dp[fr]+dp[to]-(dp[ans[i]]<<1);tmp2=dp[to]-tmp1;
		++A[fr];add1(to,tmp2);add2(ans[i],dp[fr]);add3(ans[i],tmp2);
	}
	dfs(1,0);printf("%d",fans[1]);
	for(int i=2;i<=n;++i) printf(" %d",fans[i]);
	return 0;
}