题目大意：给你一颗树，树上每个点都有一个观察员，他们仅会在 w[i] 时刻出现，观察正在跑步的玩家
一共有m个玩家，他们分别从节点 s[i] 同时出发，以每秒跑一条边的速度，沿着到 t[i] 的唯一路径向节点t[i]奔跑
如果一名玩家已经到达了终点，那么在他到达终点之后出现在终点的观察员不会观察到他
但如果在到达终点的同时观察员也出现在终点，那么观察员可以观察到他
求每个节点的观察员观察到玩家的数量
对于每个玩家的奔跑路线，可以拆成两部分
<1>向上跑，从 u 向 lca 奔跑
显然，玩家 u 能对观察员 i 产生1点贡献的充要条件为
显然，向上走的路线能对 i 点产生共贡献的条件是，起点 u 在 i 的子树中
我们只需要统计符合条件的
<2>向下跑，从 lca 向 v 奔跑
那么显然
推导可得
显然，向下走的路线能对i点产生共贡献的条件是，终点 v 在 i 的子树中
类似于上面的方法，我们只需要统计符合条件的
我们可以用vector在u,v,lca这三个点上打差分，存符合条件的值，注意值可能为负数
而其他子树的结果会影响答案，所以深搜统计一次答案，再用回溯的答案减去深搜的答案即可
方法比较奇葩大家凑合看吧。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define N 300010
#define maxn 300000
using namespace std; int n,m,cte;
int dep[N],fa[N],tp[N],sz[N],son[N],ans[N];
int w[N],s[N],t[N],F[N],bac[N*],head[N],tmp[N];
struct EDGE{
int to,nxt;
}edge[N*];
vector<int>S[N];
vector<int>E[N];
int gc()
{
int rett=,fh=;char p=getchar();
while(p<''||p>'') {if(p=='-')fh=-;p=getchar();}
while(p>=''&&p<='') {rett=rett*+p-'';p=getchar();}
return rett*fh;
}
void edge_add(int u,int v)
{
cte++;
edge[cte].to = v;
edge[cte].nxt=head[u];
head[u]=cte;
}
void Tsp1(int u,int dad)
{
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==dad) continue;
dep[v]=dep[u]+;
fa[v]=u;
Tsp1(v,u);
if(sz[v]>sz[son[u]]) son[u]=v;
sz[u]+=sz[v];
}
sz[u]++;
}
void Tsp2(int u)
{
if(son[u]) tp[son[u]]=tp[u],Tsp2(son[u]);
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==fa[u]||v==son[u]) continue;
tp[v]=v;
Tsp2(v);
}
}
int LCA(int x,int y)
{
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
x=fa[tp[x]];
}
return dep[x]<=dep[y]?x:y;
}
void dfs1(int u)
{
tmp[u]=bac[dep[u]+w[u]+maxn];
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==fa[u]) continue;
dfs1(v);
}
for(int i=;i<S[u].size();i++)
bac[S[u][i]+maxn]++;
ans[u]+=bac[dep[u]+w[u]+maxn]-tmp[u];
for(int i=;i<E[u].size();i++)
bac[E[u][i]+maxn]--;
}
void dfs2(int u)
{
tmp[u]=bac[w[u]-dep[u]+maxn];
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==fa[u]) continue;
dfs2(v);
}
for(int i=;i<E[u].size();i++)
bac[E[u][i]+maxn]--;
for(int i=;i<S[u].size();i++)
bac[S[u][i]+maxn]++;
ans[u]+=bac[w[u]-dep[u]+maxn]-tmp[u];
} int main()
{
freopen("running1.in","r",stdin);
//freopen("running6.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
memset(head,-,sizeof(head));
for(int i=;i<n;i++)
{
x=gc(),y=gc();
edge_add(x,y);
edge_add(y,x);
}
tp[]=;
Tsp1(,-);
Tsp2();
for(int i=;i<=n;i++) w[i]=gc();
for(int i=;i<=m;i++)
{
s[i]=gc(),t[i]=gc();
F[i]=LCA(s[i],t[i]);
S[s[i]].push_back(dep[s[i]]);
E[F[i]].push_back(dep[s[i]]);
}
//debug();
dfs1();
for(int i=;i<=n;i++)
{
S[i].clear(),E[i].clear();
}
memset(tmp,,sizeof(tmp));
for(int i=;i<=m;i++)
{
S[t[i]].push_back(dep[s[i]]-*dep[F[i]]);
E[F[i]].push_back(dep[s[i]]-*dep[F[i]]);
}
dfs2();
for(int i=;i<=n;i++) printf("%d ",ans[i]);
return ;
}