首先,我们考虑对于一条路径
从x->y,可以把它拆分成两部分,图中用虚线分开,然后这条路径就变成了x->lca,son[lca]->y
先来考虑从x向上走到lca的路径,对于这条路上的节点i,玩家能对节点i产生贡献的前提是deep[x]-w[i]=deep[i]
移项可得deep[x]=w[i]+deep[i],也就是说起点在w[i]+deep[i]这个深度的玩家向上走的时候都会对节点i产生1的贡献,(玩家想对节点i产生贡献,那它的深度一定等于w[i]+deep[i])
对于每一层深度建一颗线段树,动态开点,先dfs整个树,求出每个节点的dfs序,那么这就转化成区间问题,对于每一个玩家s->t,在深度为deep[s]的线段树id[s]的位置加1,id[fa[lca(s,t)]]-1,利用了差分思想,每一次求一下节点i在深度为w[i]+deep[i]的线段树里[in[i],out[i]]区间和就是答案,利用差分可以防止不合法的计算,id[fa[lca(s,t)]]-1,保证x不会被lca以上的节点计算贡献
然后考虑向下的路径,对于son[lca]->y的路径上的节点j,玩家能对j产生贡献前提是deep[x]+deep[y]-2*deep[lca(x,y)]-w[j]=deep[y]-deep[j]
移项可得deep[x]-2*deep[lca(x,y)]=w[j]-deep[j]相应的,我们在deep[x]-2*deep[lca]深度的线段树id[x]的位置加1,lca处减1,然后对于每个节点,查询w[j]-deep[j]深度的线段树[in[j],out[j]]即可
注意红字部分可能出现负数,下标统一加n
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 300005
using namespace std;
int n,m;
int fa[maxn],d[maxn*5],ans[maxn];
struct edge
{
int to,ne;
}b[maxn*2];
int kk=0,head[maxn];
struct edge2
{
int fr,to,len,anc;
}s[maxn*2];
int w[maxn];
int f[maxn][35];
inline int read()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline void add(int u,int v)
{
kk++;
b[kk].to=v;b[kk].ne=head[u];head[u]=kk;
}
inline void init()
{
memset(head,-1,sizeof(head));
memset(f,-1,sizeof(f));
}
void pre()
{
for(int i=1;i<=n;i++) f[i][0]=fa[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
if(f[i][j-1]!=-1) f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y)
{
//printf("%d %d\n",x,y);
if(d[x]<d[y]) swap(x,y);
int dc=d[x]-d[y];
for(int i=0;dc;i++)
if((dc&(1<<i))){
dc^=(1<<i);
x=f[x][i];
}
if(x==y) return x;
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i]&&f[x][i]!=-1){
x=f[x][i]; y=f[y][i];
}
return fa[x];
}
int q[maxn],h[maxn],id=0;
void dfs(int x)
{
q[x]=++id;
for(int i=head[x];i!=-1;i=b[i].ne)
if(b[i].to!=fa[x]){
fa[b[i].to]=x; d[b[i].to]=d[x]+1;
dfs(b[i].to);
}
h[x]=id;
}
int root[maxn*30],sum[maxn*30],ls[maxn*30],rs[maxn*30];
int cnt=0;
struct Tree
{
void update(int k)
{
sum[k]=sum[ls[k]]+sum[rs[k]];
}
void insert(int &k,int l,int r,int x,int w)
{
if(!x) return ;
if(!k) k=++cnt;
sum[k]+=w;
if(l==r) return ;
int mid=(l+r)/2;
if(x<=mid) insert(ls[k],l,mid,x,w);
else insert(rs[k],mid+1,r,x,w);
update(k);
}
int quiry(int k,int l,int r,int ll,int rr)
{
if(!k) return 0;
if(ll<=l&&r<=rr) return sum[k];
int ans=0;
int mid=(l+r)/2;
if(ll<=mid) ans+=quiry(ls[k],l,mid,ll,rr);
if(rr>mid) ans+=quiry(rs[k],mid+1,r,ll,rr);
return ans;
}
}tr;
inline void init2()
{
memset(root,0,sizeof(root));
memset(sum,0,sizeof(sum));
memset(ls,0,sizeof(ls));
memset(rs,0,sizeof(rs));
cnt=0;
}
int main()
{
freopen("runninga.in","r",stdin);
freopen("runninga.out","w",stdout);
init();
n=read();m=read();
int x,y,anc;
for(int i=1;i<n;i++){
x=read(); y=read();
add(x,y); add(y,x);
}
dfs(1);
pre();
for(int i=1;i<=n;i++) w[i]=read();
for(int i=1;i<=m;i++){
s[i].fr=read(); s[i].to=read();
anc=lca(s[i].fr,s[i].to);
s[i].len=d[s[i].fr]+d[s[i].to]-2*d[anc];
s[i].anc=anc;
tr.insert(root[d[s[i].fr]],1,n,q[s[i].fr],1);
tr.insert(root[d[s[i].fr]],1,n,q[fa[anc]],-1);
}
for(int i=1;i<=n;i++) ans[i]+=tr.quiry(root[w[i]+d[i]],1,n,q[i],h[i]);
init2();
for(int i=1;i<=m;i++){
int t=d[s[i].fr]-(d[s[i].anc]<<1)+(n<<1);
tr.insert(root[t],1,n,q[s[i].to],1);
tr.insert(root[t],1,n,q[s[i].anc],-1);
}
for(int i=1;i<=n;i++)
ans[i]+=tr.quiry(root[w[i]-d[i]+(n<<1)],1,n,q[i],h[i]);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}