线段树合并

从节点角度出发考虑，如果第 $w_i$ 秒点 $i$ 有人出发，那么肯定是能被 $i$ 上的观察员观察到的。更进一步地，对于其孩子节点 $j$，如果第 $w_i - 1$ 秒点 $j$ 有人出发，也能被 $i$ 上的观察员观察到。

使用 $d_i$ 表示节点 $i$ 的深度，把 $u \rightarrow v$ 的路径拆成 $u \rightarrow \operatorname{lca}(u,v)$ 的上行路径和 $\operatorname{lca}(u,v) \rightarrow v$ 的下行路径分别考虑。

对于上行路径中的节点 $i$，其观测到 $j$ 出发的跑者当且仅当 $w_i - (d_j - d_i) = 0$，其中 $d_j$ 的数量为 $O(n)$ 等级，相对 $d_i,w_i$ 较难维护。变换式子得到 $w_i + d_i = d_j$，线段树合并维护 $d_j$ 可以得到很优的做法。

对于下行路径中的节点 $i$，其观测到 $j$ 出发的跑者当且仅当 $w_i -(d_j - d_{\operatorname{lca}(i,j)}) - (d_i - d_{\operatorname{lca}(i,j)}) = 0$，变换得到 $w_i - d_i = d_j - 2d_{\operatorname{lca}(i,j)}$，线段树合并维护 $d_j - 2d_{\operatorname{lca}(i,j)}$，注意这个值可能是负数，线段树维护下行路线信息时需要加上 $n+1$ 的偏移量。

差分所有操作，在 $s_i$ 处的线段树插入 $d_{s_i}$，在 $t_i$ 处的线段树插入 $d_{s_i} - 2d_{\operatorname{lca}(s_i,t_i)}$，在 $\operatorname{lca}(s_i,t_i)$ 处计算答案后删除这两个值。注意 $\operatorname{lca}(s_i,t_i)$ 能观测到跑者时会重复统计这个询问的贡献，输入询问时判断 $\operatorname{lca}(s_i,t_i)$ 是否能观测到跑者，如果是则提前将 $\operatorname{lca}(s_i,t_i)$ 的答案减一。由于上行下行路线的答案统计会相互影响，它们的权值要分开统计。

由于 $n,m$ 同阶，时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int wu,wd,ls,rs;}s[600'005*20*2];
vector<int> v[300'005],au[300'005],ad[300'005],du[300'005],dd[300'005];
int d[300'005],f[300'005],w[300'005],top[300'005],wson[300'005];
int n,m,seg,lim,ext,a[300'005],ro[300'005],ans[300'005];
void fisdfs(int x,int las){
    w[x]=1,f[x]=las,d[x]=d[las]+1;
    for(int i:v[x]) if(i!=las){
        fisdfs(i,x),w[x]+=w[i];
        if(w[i]>w[wson[x]]) wson[x]=i;
    }
}
void secdfs(int x,int las){
    top[x]=las;
    if(wson[x]==0) return;
    secdfs(wson[x],las);
    for(int i:v[x]) if(i!=f[x]&&i!=wson[x]) secdfs(i,i);
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return d[x]<d[y] ? x:y;
}
void update(int &u,int l,int r,int p,int ku,int kd){
    if(u==0) u=++seg;
    if(l==r) return s[u].wu+=ku,s[u].wd+=kd,void();
    int mid=(l+r)>>1;
    if(p<=mid) update(s[u].ls,l,mid,p,ku,kd);
    else update(s[u].rs,mid+1,r,p,ku,kd);
}
Segment query(int u,int l,int r,int p){
    if(l==r) return s[u];
    int mid=(l+r)>>1;
    if(p<=mid) return query(s[u].ls,l,mid,p);
    return query(s[u].rs,mid+1,r,p);
}
int merge(int x,int y,int l,int r){
    if(x==0||y==0) return x+y;
    if(l==r) return s[x].wu+=s[y].wu,s[x].wd+=s[y].wd,x;
    int mid=(l+r)>>1;
    s[x].ls=merge(s[x].ls,s[y].ls,l,mid);
    s[x].rs=merge(s[x].rs,s[y].rs,mid+1,r);
    return x;
}
void dfs(int x,int las){
    for(int i:v[x]) if(i!=las) dfs(i,x),ro[x]=merge(ro[x],ro[i],1,lim);
    for(int i:au[x]) update(ro[x],1,lim,i,1,0);
    for(int i:ad[x]) update(ro[x],1,lim,i+ext,0,1);
    ans[x]+=query(ro[x],1,lim,a[x]+d[x]).wu;
    ans[x]+=query(ro[x],1,lim,a[x]-d[x]+ext).wd;
    for(int i:du[x]) update(ro[x],1,lim,i,-1,0);
    for(int i:dd[x]) update(ro[x],1,lim,i+ext,0,-1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m,ext=n+1,lim=n*2+1;
    for(int i=1;i<=n-1;i++){
        static int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    fisdfs(1,0),secdfs(1,1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        static int x,y,poi;
        cin>>x>>y,poi=lca(x,y);
        au[x].push_back(d[x]);
        ad[y].push_back(d[x]-2*d[poi]);
        du[poi].push_back(d[x]);
        dd[poi].push_back(d[x]-2*d[poi]);
        if(a[poi]+d[poi]==d[x]) --ans[poi];
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}