题：https://www.luogu.com.cn/problem/P1600
题意：给定n个节点的树和每个节点会在a[i]时刻进行观察，然后再给出m个点沿从S->T的简单路径移动，所有点同时开始且每一秒经过一条边，问每一个节点上的观察员会观察的几个点？
分析：我们考虑S到lca（S，T）再到T的路径，考虑路径上S到LCA（S，T）的点u，要是u能观察到的充分必要条件就是deep[S]-deep[u]==a[u]，所以我们在统计的时候我们把deep[S]加入到桶S中；
对于LCA（S，T）到T的路径上的点同样的充分必要条件为deep[T]-deep[u]=dis(S,T)-a[u].（化简一下：deep[S]-2*deep[lca]==a[u]+deep[u]），把答案加到桶T中；
同时，我们要注意到，我们统计是对当前dfs到的点的ans[u]进行统计，有俩部分路劲来源，所以要俩部分来源都要加到ans[u]上，而我们现在做的相当于在dfs lca，而lca单单这个点会对俩部分同时计算，这是不正确的（因为一条路径只有一个贡献，而现在你有可能加上了俩个贡献）。所以要进行差分，具体地就在lca的S桶要消去[deep[S]]的贡献去（在S的S桶中加什么就消什么），在fa[lca]减去[deep[S]-2*deep[lca]]的贡献
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int M=3e5+5; inline int read(){ int sum=0,x=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=0; ch=getchar(); } while(ch>='0'&&ch<='9') sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); return x?sum:-sum; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int n,m; vector<int>g[M],signS[M],unsignS[M],signT[M],unsignT[M]; int sz[M],deep[M],son[M],tp[M],S[M],cnt[M<<1],*T=&cnt[M],a[M],vis[M],ans[M],fa[M]; void dfs1(int u,int ff){ sz[u]=1,fa[u]=ff,deep[u]=deep[ff]+1; for(auto v:g[u]){ if(v!=ff){ dfs1(v,u); sz[u]+=sz[v]; if(!son[u]||sz[son[u]]<sz[v]) son[u]=v; } } } void dfs2(int u,int top){ tp[u]=top; if(son[u]) dfs2(son[u],top); for(auto v:g[u]){ if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } int LCA(int x,int y){ while(tp[x]!=tp[y]){ if(deep[tp[x]]>deep[tp[y]]) x=fa[tp[x]]; else y=fa[tp[y]]; } return deep[x]>deep[y]?y:x; } void cal(int u,int cc){ for(auto v:signS[u])S[v]+=cc; for(auto v:unsignS[u])S[v]-=cc; for(auto v:signT[u])T[v]+=cc; for(auto v:unsignT[u])T[v]-=cc; for(auto v:g[u]){ if(v!=fa[u]&&!vis[v]) cal(v,cc); } } void dfs3(int u,int sign){ for(auto v:g[u]){ if(v!=fa[u]&&v!=son[u]) dfs3(v,0); } if(son[u]) dfs3(son[u],1),vis[son[u]]=1; cal(u,1); if(a[u]+deep[u]<=n) ans[u]=S[a[u]+deep[u]]; ans[u]+=T[a[u]-deep[u]]; vis[son[u]]=0; if(!sign) cal(u,-1); } int main(){ n=read(),m=read(); for(int u,v,i=1;i<n;i++){ u=read(),v=read(); g[u].pb(v); g[v].pb(u); } dfs1(1,0); dfs2(1,1); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1,u,v;i<=m;i++){ u=read(),v=read(); int lca=LCA(u,v); signS[u].pb(deep[u]); unsignS[lca].pb(deep[u]); signT[v].pb(deep[u]-(deep[lca]<<1)); unsignT[fa[lca]].pb(deep[u]-(deep[lca]<<1)); } dfs3(1,1); for(int i=1;i<=n;i++) write(ans[i]),putchar(' '); return 0; }