来一种$O(nlogn)$的毒瘤做法。
首先介绍一下主角：$dsu\ on\ tree$ 。其原理是树上启发式合并。它支持$O(nlogn)$无修改子树信息统计。
实现：树剖划分出轻重儿子。对于某个节点，先递归处理轻儿子，并清除轻子树的影响。然后处理重儿子，保留重子树的影响。再次统计轻子树的影响，就能得到该点整个子树的信息。
伪代码：
void dfs(int x,bool remain){
//remain表示是否保留该点子树的信息
int f=fa[x],s=son[x];//s为重儿子
for(int i=h[x];i;i=e[i].pre){
int y=e[i].to;
if(x!=f&&x!=s)dfs(y,0);//递归处理轻儿子，删除信息
}
if(s)dfs(s,1);//递归处理重儿子并保留信息
count(x);//这里的count是统计x的轻子树的信息
ans[x]=...;//记录答案
if(!remain)clear(x);//清除x整个子树的影响
}
复杂度：每个点到根节点的路径被剖成了最多$logn$条重链，而其中每个轻边都会使该点被用至多$O(n)$的时间统计一次，只要单点的信息统计与删除是$O(1)$的，总复杂度就为$O(nlogn)$
参考：
http://www.cnblogs.com/zzqsblog/p/6146916.html
https://www.cnblogs.com/zcysky/p/6822395.html
回到这个题上。对于每一个玩家$(x->y)$，我们可以把它分成两半：$(x->lca(x,y))+(lca(x,y)->y)$，因为前者是往上跑，后者是往下跑，分开好处理。
放个图：
红色的数字是跑到该点的时间。
（以下用$deep$代表点的深度）
先处理$(x->lca(x,y))$
对于往上跑的路径来说，只要满足$deep[x]-deep[i]=w[i]$，且该路径能覆盖到$i$，$i$就能观测到该名玩家。
即$deep[i]+w[i]=deep[x]$
再处理$(lca(x,y)->y)$
如图容易发现：从点$y$往上跳，每跳一步，时间就会$-1$，而一开始时间为$dis(x,y)$。
则一个点$i$能观测到$y$的条件是：
$deep[y]-deep[i]=dis(x,y)-w[i]$且该路径也要覆盖$i$。
其中$dis(x,y)=deep[x]+deep[y]-2*deep[lca(x,y)]$
移项整理得：
$deep[x]-2*deep[lca(x,y)]=w[i]-deep[i]$
综上，运用树上差分的思想，对于每个玩家$(x->y)$，用两个数组$up$和$down$：
- 将点$x$的$up$插入一个$deep[x]$。
- 将点$y$的$down$插入一个$deep[x]-2*deep[lca(x,y)]$。
- $lca(x,y)$会统计两遍该路径，在$up$中打上删除$deep[x]$的标记
- 为了保证路径不覆盖的点不会统计，将$fa[lca(x,y)$]打上删除$deep[x]-2*deep[lca(x,y)]$的标记。
对于一个点$i$，统计其子树的$up$、$down$所有插入过的数，答案即为$up$中$(deep[i]+w[i])$的数量加上$down$中$(w[i]-deep[i])$的数量。
怎么统计呢？$dsu\ on\ tree$就出场了！直接统计就好了。
时间复杂度：每位玩家最多影响四个点，均摊下来单点统计还是$O(1)$的，总复杂度$O(nlogn)$。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 300005
#define inf 0x3f3f3f
#define pn putchar('\n')
#define px(x) putchar(x)
#define ps putchar(' ')
#define pd puts("======================")
#define pj puts("++++++++++++++++++++++")
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int h[maxn],w[maxn],top[maxn],deep[maxn],fa[maxn],siz[maxn],son[maxn],num,n,m,ans[maxn];
bool vis[maxn];
int upi[maxn];
vector<int>doi[maxn],dod[maxn],upd[maxn];
//upi：up insert，向上路径的插入。因为该插入只会插入某个点的deep，所以压成了普通的数组
//upd：up delete，向上路径的删除
//doi、dod同理
struct edge{
int pre,to;
}e[maxn<<1];
inline void add(int from,int to){
e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
struct Tree_Chain_Split{
void dfs1(int node=1){
siz[node]=1;
for(register int i=h[node];i;i=e[i].pre){
int x=e[i].to;
if(!siz[x]){
fa[x]=node,deep[x]=deep[node]+1;
dfs1(x);
if(siz[x]>siz[son[node]])son[node]=x;
siz[node]+=siz[x];
}
}
}
void dfs2(int node=1){
vis[node]=1;
if(son[node]){
top[son[node]]=top[node];
dfs2(son[node]);
for(register int i=h[node];i;i=e[i].pre){
int x=e[i].to;
if(!vis[x]){
top[x]=x;
dfs2(x);
}
}
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}
return deep[x]<deep[y]?x:y;
}
}tcs;
//树链剖分，顺便用的树剖的lca
int upcnt[maxn],CNT[maxn<<1],*downcnt=&CNT[maxn];
//upcnt是向上路径统计数组，downcnt反之。两种路径统计依据不同，所以分开
//因为w[i]-deep[i]可能为负数，所以用了指针小技巧使downcnt能使用负数下标
bool in[maxn];
//用于dsu on tree的数组。标记上的点在统计子树信息时不会访问该点的子树（见count函数）
void count(int node){
int f=fa[node];
for(register int i=h[node];i;i=e[i].pre){
int x=e[i].to;
if(x!=f&&!in[x])count(x);
}
upcnt[deep[node]]+=upi[node];
for(register int i=0;i<upd[node].size();++i)
--upcnt[upd[node][i]];
for(register int i=0;i<doi[node].size();++i)
++downcnt[doi[node][i]];
for(register int i=0;i<dod[node].size();++i)
--downcnt[dod[node][i]];
}//统计信息
void clear(int node){
int f=fa[node];
for(register int i=h[node];i;i=e[i].pre){
int x=e[i].to;
if(x!=f)clear(x);
}
upcnt[deep[node]]-=upi[node];
for(register int i=0;i<upd[node].size();++i)
++upcnt[upd[node][i]];
for(register int i=0;i<doi[node].size();++i)
--downcnt[doi[node][i]];
for(register int i=0;i<dod[node].size();++i)
++downcnt[dod[node][i]];
}
void dfs(int node=1,bool remain=0){
int s=son[node],f=fa[node];
if(s){
for(register int i=h[node];i;i=e[i].pre){
int x=e[i].to;
if(x!=s&&x!=f)dfs(x,0);
}
dfs(s,1);
in[s]=1;//count时不会统计上它的重子树
}
count(node);//统计轻儿子的信息
if(deep[node]+w[node]<=n)ans[node]=upcnt[deep[node]+w[node]];
//判一下不能越界
ans[node]+=downcnt[w[node]-deep[node]];
//获取答案
in[s]=0;//一定要清掉标记
if(!remain)clear(node);//清除整个子树的信息
}
void init(){
while(m--){
int a=read(),b=read(),l=tcs.lca(a,b);
++upi[a];
doi[b].push_back(deep[a]-(deep[l]<<1));
upd[l].push_back(deep[a]);
dod[fa[l]].push_back(deep[a]-(deep[l]<<1));
}
}//读入每名玩家并处理
int main(){
n=read(),m=read();
for(register int i=1;i<n;++i){
int a=read(),b=read();
add(a,b),add(b,a);
}
for(register int i=1;i<=n;++i)
w[i]=read();
tcs.dfs1(),tcs.dfs2();
init(),dfs();
for(register int i=1;i<=n;++i)
printf("%d ",ans[i]);
}
码量确实有点大。不过$dsu\ on\ tree$在某些题中还是很高效的$QwQ$。
