主要讲一讲

树上差分

顾名思义，树上差分就是在树上的差分（？？？）

学过树状数组（区间修改）的同学应该了解，差分具有很优秀的性质

已知原数组 a[i],设差分数组 b[i]=a[i]-a[i-1]

那么就有 a[i]=b[1]+b[2]+...+b[n]

修改也很方便，例如对于区间（p,q）同时加上x,相当于 b[p]+=n,b[q+1]-=n

接下来就是把线性的差分移到树上，

同理，已知原数组a[i]表示每个点的点权，

我们设差分数组b[i]=a[i]-sum(a[j])(j为i的每个直接相连的儿子)；

不难发现，叶子节点的b[i]恰好为该点点权a[i],此外，对于任意一个节点K，

a[K]=以K为根节点的子树中所有b[i]之和。

如果我们要对树上的一条链(u,v)的点权进行修改(同时加上x)，只需要：

b[u]+=x;

b[v]+=x;

b[lca(u,v)]-=x;

b[fa[lca(u,v)]]-=x;

注意为了不影响到链外的其他点权，lca（u,v）的父节点需要修改，可以自己推一下。

这是点权的情况，如果是边权，只需要把一个点到父亲的边权赋给自己当作点权，

然后当作点权的情况做就好了，细节需要处理一下。

在本题中，原数组初始都是0，所以我们只需要读入、处理，最后遍历整颗树，递

归求出a[i]就ok了

代码：

#include <bits/stdc++.h>
using namespace std;
int h[300000+5],fa[300000+5][25];
int vis[300000+5],lg[300000+5],dep[300000+5];
int a[300000+5],b[300000+5];//a为糖果数,b为差分数组
int m,n,i,j,x,y,tmp;
struct EDGE{
    int from,to,next;
};
EDGE e[600000+5];
void add(int a,int b){
    tmp++;
    e[tmp].from=a;
    e[tmp].to=b;
    e[tmp].next=h[a];
    h[a]=tmp;
}
void dfs1(int k){
    int s=h[k];
    while(s!=0){
        int t=e[s].to;
        if(t!=fa[k][0]){
            fa[t][0]=k;
            dep[t]=dep[k]+1;
            dfs1(t);
        } 
        s=e[s].next;
    }
}
int lca(int a,int b){
    if(dep[a]<dep[b]){
        int t=a;
        a=b;
        b=t;
    }
    while(dep[a]!=dep[b]){
        int k=lg[dep[a]-dep[b]]-1;
        a=fa[a][k];
    }
    if(a==b) return a;
    else{
        for(j=lg[dep[a]]-1;j>=0;j--){
            if(fa[a][j]!=fa[b][j]){
                a=fa[a][j];
                b=fa[b][j];
            }
        }
    }
    return fa[a][0];
}
void dfs2(int k){
    int s=h[k];
    while(s!=0){
        int t=e[s].to;
        if(t!=fa[k][0]){
            dfs2(t);
            b[k]+=b[t];
        }
        s=e[s].next;
    }
}
int main(){
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d",&vis[i]); 
    for(i=1;i<=n-1;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(1);
    for(j=1;j<=20;j++)
        for(i=1;i<=n;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    for(i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    a[vis[1]]++;
    for(i=2;i<=n;i++){
    	int now=lca(vis[i],vis[i-1]);
    	b[vis[i]]++;
    	b[vis[i-1]]++;
    	b[now]--;
    	b[fa[now][0]]--;
    	a[vis[i-1]]--;//链首糖果数直接减1
    }
    a[vis[n]]--;
    dfs2(1);
    for(i=1;i<=n;i++)
        cout<<a[i]+b[i]<<endl;
    return 0;
}

明天生日写篇题解开心一下