【题意】n个点的树，有m个人同时开始走链，每一步花一秒，n个点都有观察员在ai秒观察，求每个观察员观察到的人数。

【算法】树上差分（主席树||线段树合并） 

【题解】一个人的走链可以拆成u-lca和lca-v两部分，可以发现在u-lca链上的点能观察到这个人的w[x]，满足所有deep[x]+w[x]相等。同理，在lca-v链上需满足deep[x]-w[x]相等。（画个图，将深度和秒数都标出来就可以得到结论了）

所以可以得到一个点观察到链u-v的条件是【在u-lca上且deep[x]+w[x]=deep[u]】或【在lca-v上且deep[x]-w[x]=deep[v]-time】，其中time=deep[u]+deep[v]-2*deep[lca]。

为了判断是否满足条件，我们可以维护数组A（针对deep[x]+w[x]）和数组B（针对deep[x]-w[x]）作为判断数组。对于每条链A[deep[u]]+1和B[deep[v]-time]+1，然后点x就可以直接判断满足多少链的要求。

接下来需要解决是否在u-lca或lca-v上的问题，可以运用树上差分。对于一条链，在u点标记A[deep[u]]+1的操作，在v点标记B[deep[v]-time]+1的操作，在lca标记A[deep[u]]-1的操作，在fa[lca]标记B[deep[v]-time]-1的操作（否则lca点同时满足两个要求会计算两次），标记操作需要用类似邻接表的链表接在每个节点处。

然后总的进行一次dfs，每个节点按顺序进行：统计ans[x]，将标记操作，dfs子节点，ans[x]=统计ans[x]-ans[x](原)。

★注意：

1.树上差分只能是u+1，v+1，lca-2（或lca-1&&fa(lca)-1），绝对不能是lca处加，因为lca处加会影响到所有子树而不止一条链。

2.树上差分的操作顺序必须是：【统计ans】【操作标记】【DFS子节点】【统计ans-原ans】

对点x，最后统计ans是x的子树和x上面已统计的部分。减原ans相当于减掉x上面已统计的部分。

为什么必须这样做？要是在返回的时候操作标记，就会干扰父节点另一棵子树，所以必须用 [ 当前已统计的所有-x上方已统计的所有 ] 这种后统计-先统计的强操作。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=300010;int first[maxn],firstA[maxn],firstB[maxn],a[maxn],markA[maxn*2],markB[maxn*2],tot,totA,totB;int deep[maxn],f[maxn][30],ans[maxn],n,m;struct edge{
    int v,w,from;}e[maxn*2],A[maxn*2],B[maxn*2];void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void insertA(int u,int v,int w){totA++;A[totA].v=v;A[totA].w=w;A[totA].from=firstA[u];firstA[u]=totA;}void insertB(int u,int v,int w){totB++;B[totB].v=v;B[totB].w=w;B[totB].from=firstB[u];firstB[u]=totB;}void DFS(int x,int fa){    for(int j=1;(1<
          
           <=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1];    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){        deep[e[i].v]=deep[x]+1;        f[e[i].v][0]=x;        DFS(e[i].v,x);    }}int lca(int x,int y){    if(deep[x]
           
            =0;i--)if((1<
            
             <=deep[x]&&f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } return f[x][0];}void dfs(int x,int fa){ ans[x]=markA[a[x]+deep[x]]+markB[a[x]-deep[x]+n];// for(int i=firstA[x];i;i=A[i].from){ if(A[i].w)markA[A[i].v]--;else markA[A[i].v]++; } for(int i=firstB[x];i;i=B[i].from){ if(B[i].w)markB[B[i].v]--;else markB[B[i].v]++; } for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa)dfs(e[i].v,x); ans[x]=markA[a[x]+deep[x]]+markB[a[x]-deep[x]+n]-ans[x];}int main(){ n=read();m=read(); for(int i=1;i
            
           
          
         
        
       
      

 

顺便一提主席树和线段树合并的做法。

主席树：对每个点询问子树内等于某个值的起点数和等于某个值的终点树，转化为dfs序上的区间权值询问，可以用可持久化权值线段树解决。

线段树合并：线段树下标记录关键值（和差分的两个值一样），然后从叶子往上进行线段树合并和查询，非常套路了。