wucstdio @ 2018-07-18 20:55:20
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node
{
int dep;
int parent;
int w;
int headu,headv,headlca;
int ans;
}a[700005];
struct Edge
{
int to;
int next;
}e[2000005];
struct Query
{
int u,v,lca,t;
int nextu,nextv,nextlca;
}q[700005];
int n,m,edgenum,head[700005],_num[1400005],_numu[1400005],_numv[1400005],_numlca[1400005];
int*num=_num+700000,*numu=_numu+700000,*numv=_numv+700000,*numlca=_numlca+700000;//有可能出现负数
int anc[30][700005],log2[700005];
void add(int u,int v)//加边
{
e[++edgenum].to=v;
e[edgenum].next=head[u];
head[u]=edgenum;
}
void pre()//LCA预处理
{
for(int i=2;i<=n;i++)
log2[i]=log2[i>>1]+1;
for(int i=1;i<=n;i++)
anc[0][i]=a[i].parent;
for(int i=1;i<log2[n];i++)
{
for(int j=1;j<=n;j++)
anc[i][j]=anc[i-1][anc[i-1][j]];
}
}
int LCA(int u,int v)//树上倍增LCA
{
if(a[u].dep<a[v].dep)swap(u,v);
for(int i=0;a[u].dep-a[v].dep;i++)
{
if((1<<i)&a[u].dep-a[v].dep)
{
u=anc[i][u];
}
}
if(u==v)return u;
for(int i=log2[n];i>=0;i--)
if(anc[i][u]!=anc[i][v])
u=anc[i][u],v=anc[i][v];
return a[u].parent;
}
void dfs(int node)//dfs建树
{
a[node].dep=a[a[node].parent].dep+1;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==a[node].parent)continue;
a[to].parent=node;
dfs(to);
}
}
void work(int node)//深搜计数
{
int preu=numu[a[node].dep+a[node].w];
int prev=numv[a[node].dep-a[node].w];
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==a[node].parent)continue;
work(to);
}
for(int hd=a[node].headu;hd;hd=q[hd].nextu)
numu[a[node].dep]++;
for(int hd=a[node].headv;hd;hd=q[hd].nextv)
numv[a[node].dep-q[hd].t]++;
a[node].ans+=numu[a[node].dep+a[node].w]-preu;
a[node].ans+=numv[a[node].dep-a[node].w]-prev;
for(int hd=a[node].headlca;hd;hd=q[hd].nextlca)
{
if(a[q[hd].u].dep==a[node].dep+a[node].w) a[node].ans--;
numu[a[q[hd].u].dep]--;
numv[a[q[hd].v].dep-q[hd].t]--;
}
}
void add2(int i)//用链表把每一个人加到对应的节点上
{
q[i].nextlca=a[q[i].lca].headlca;
a[q[i].lca].headlca=i;
q[i].nextu=a[q[i].u].headu;
a[q[i].u].headu=i;
q[i].nextv=a[q[i].v].headv;
a[q[i].v].headv=i;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].w);
pre();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].u,&q[i].v);
q[i].lca=LCA(q[i].u,q[i].v);
q[i].t=a[q[i].u].dep+a[q[i].v].dep-a[q[i].lca].dep*2;
add2(i);
}
work(1);
for(int i=1;i<=n;i++)
printf("%d ",a[i].ans);
printf("\n");
return 0;
}