|
i=head[u];i;i=Next[i])
27 {
28 int v=to[i];
29 if(v==FA)continue;
30 fa[v][0]=u;
31 dep[v]=dep[u]+1;
32 dfs1(v,u);
33 }
34 }
35 void dfs2(int u,int FA)
36 {
37 int now=dep[u]+w[u],last=Bu[now];
38 for(int i=head[u];i;i=Next[i])
39 {
40 int v=to[i];
41 if(v==FA)continue;
42 dfs2(v,u);
43 }
44 Bu[dep[u]]+=CNT[u];
45 ans[u]=Bu[now]-last;
46 for(int i=0;i<que1[u].size();i++) Bu[dep[que1[u][i]]]--;
47 }
48 void dfs3(int u,int FA)
49 {
50 int now=dep[u]-w[u],last=Bu[now+eps];
51 for(int i=head[u];i;i=Next[i])
52 {
53 int v=to[i];
54 if(v==FA)continue;
55 dfs3(v,u);
56 }
57 for(int i=0;i<que2[u].size();i++) Bu[que2[u][i]+eps]++;
58 ans[u]+=Bu[now+eps]-last;
59 for(int i=0;i<que3[u].size();i++) Bu[que3[u][i]+eps]--;
60 }
61 int getlca(int x,int y)
62 {
63 if(dep[x]<dep[y])swap(x,y); int Val=dep[x]-dep[y];
64 for(int j=0;j<=19;j++) if(Val&(1<<j)) x=fa[x][j]; if(x==y)return x;
65 for(int j=19;j>=0;j--) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
66 return fa[x][0];
67 }
68 int main()
69 {
70 //fre("1");
71 scanf("%d%d",&n,&m); for(int i=1,a,b;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); }
72 for(int i=1;i<=n;i++)scanf("%d",&w[i]);
73 dep[1]=1; dfs1(1,0);
74 for(int j=1;j<=19;j++)
75 for(int i=1;i<=n;i++)
76 fa[i][j]=fa[fa[i][j-1]][j-1];
77 for(int i=1;i<=m;i++)
78 {
79 scanf("%d%d",&S[i],&T[i]);
80 CNT[S[i]]++;//这一个点有多少个起点。
81 LCA[i]=getlca(S[i],T[i]);
82 len[i]=dep[S[i]]+dep[T[i]]-2*dep[LCA[i]];
83 que1[LCA[i]].push(S[i]);
84 }
85 dfs2(1,0);
86 memset(Bu,0,sizeof Bu);
87 for(int i=1;i<=m;i++)
88 {
89 que2[T[i]].push(dep[T[i]]-len[i]);
90 que3[LCA[i]].push(dep[T[i]]-len[i]);
91 }
92 dfs3(1,0);
93 for(int i=1;i<=m;i++)
94 if(dep[S[i]]-dep[LCA[i]]==w[LCA[i]])
95 ans[LCA[i]]--;
96 for(int i=1;i<=n;i++)
97 printf("%d ",ans[i]);
98 return 0;
99 }
View Code
|