记录编号	437444	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	天亮说晚安·	是否通过	通过
代码语言	C++	运行时间	2.672 s
提交时间	2017-08-14 10:15:15	内存使用	56.39 MiB

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#define maxn 300005
using namespace std;

inline int read(){
    char x=getchar();int sum=0,f=1;
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
    return f*sum;
}

vector<int>cc[maxn],dian[maxn],dian2[maxn];
int n,m,head[maxn],size,a[maxn],S[maxn],T[maxn],ans[maxn];
int dep[maxn],fa[maxn][20],dada,lca[maxn],shu[maxn*3];
int times[maxn];
struct Edge{
     int u,v,next;
}edge[maxn*3];
inline void add(int u,int v){
     edge[++size].u=u;edge[size].v=v;
     edge[size].next=head[u];head[u]=size;
}

inline void dfs1(int x,int depth){
     dep[x]=depth; 
     for(int i=head[x];i;i=edge[i].next){
	     int v=edge[i].v;
	     if(v==fa[x][0])  continue;
	     fa[v][0]=x; dfs1(v,depth+1);
	 }
}

inline int LCA(int x,int y){
     if(dep[x]<dep[y])  swap(x,y);
     for(int i=dada;i>=0;i--)
        if(dep[x]-(1<<i)>=dep[y])
           x=fa[x][i];
     if(x==y)  return x;
     for(int i=dada;i>=0;i--)
        if(fa[x][i]&&fa[x][i]!=fa[y][i])
           x=fa[x][i],y=fa[y][i];
     return fa[x][0];
}

void init(){
     dfs1(1,1);
     for(int i=1;i<=dada;i++)
        for(int j=1;j<=n;j++){
            if(!fa[fa[j][i-1]][i-1]) continue;
            fa[j][i]=fa[fa[j][i-1]][i-1];
		}
	 for(int i=1;i<=m;i++){ 
	    lca[i]=LCA(S[i],T[i]);
        cc[lca[i]].push_back(i);
        times[i]=dep[S[i]]+dep[T[i]]-2*dep[lca[i]];
	 }
}

inline void dfs2(int x){
	 int r=shu[a[x]+dep[x]];
     for(int i=head[x];i;i=edge[i].next){
	     int v=edge[i].v;
	     if(v==fa[x][0])  continue;
		 dfs2(v); 
	 }
	 int tot=dian[x].size();
     for(int i=0;i<tot;i++){
	    int u=dian[x][i];
    	if(dep[lca[u]]<=dep[S[u]])  shu[dep[S[u]]]++;
	 }
	 ans[x]+=(shu[a[x]+dep[x]]-r)>0?(shu[a[x]+dep[x]]-r):0;
	 tot=cc[x].size();
	 for(int i=0;i<tot;i++){
	    int u=cc[x][i];
	    if(dep[lca[u]]<=dep[S[u]]) shu[dep[S[u]]]--;
     }
}

inline void dfs3(int x){
     int r=shu[a[x]-dep[x]+maxn];
     for(int i=head[x];i;i=edge[i].next){
	     int v=edge[i].v;
	     if(v==fa[x][0]) continue;
	     dfs3(v);
	 }
	 int tot=dian2[x].size();
	 for(int i=0;i<tot;i++){
	     int u=dian2[x][i];
	     if(dep[lca[u]]<=dep[T[u]])  shu[times[u]-dep[T[u]]+maxn]++;
	 }
	 ans[x]+=(shu[a[x]-dep[x]+maxn]-r)>0?(shu[a[x]-dep[x]+maxn]-r):0;
	 tot=cc[x].size();
	 for(int i=0;i<tot;i++){
	    int u=cc[x][i];
	    if(dep[lca[u]]<=dep[T[u]]) shu[times[u]-dep[T[u]]+maxn]--;
	 }
}

int main(){
freopen("runninga.in","r",stdin);
freopen("runninga.out","w",stdout);
     n=read(),m=read(); int oo=1;
	 for(int i=1;i<=m;i++){oo=oo*2; if(oo>n) break; dada=i;}	
	 for(int i=1;i<n;i++){
	     int x=read(),y=read();
	     add(x,y);  add(y,x);
	 }
	 for(int i=1;i<=n;i++)  a[i]=read();
	 for(int i=1;i<=m;i++){
	    S[i]=read(),T[i]=read();
		dian[S[i]].push_back(i);dian2[T[i]].push_back(i);
     }
	 init();  dfs2(1);
	 memset(shu,0,sizeof(shu));  
	 dfs3(1);
	 for(int i=1;i<=m;i++)
	     if(a[lca[i]]==dep[S[i]]-dep[lca[i]]) ans[lca[i]]--;
	 for(int i=1;i<=n;i++)
         printf("%d ",ans[i]);
}