树上差分 | wjyppm's Blog

1.树上差分概念

树上差分，字面意思就是在树上做差分。

所以她能干啥能，举个例子，如果题目问经过树上某个点或某个边的次数，树上差分就可以派上用场啦。

树上差分就是利用差分的性质，前缀和的思想。只对树上一部分节点进行修改。而不是暴力全改，能将 $O(n)$ 的修改降为 $O(1)$

这个在日后会经常用到，要好好学习。

2.点差分

咱们一个一个加肯定包会TLE的，但是我们在讲树上差分啊！

那么我们如何进行差分呢，差分是在一条链上的在树上怎么操作呢？唉！就是将树拆成链

如下

对路径 $3\rightarrow 6$ 路径进行加一的操作我们先找到3和6的LCA即2，将这个路径转化为2条链，一个是 $2\rightarrow 3$ 和 $5\rightarrow 6$ ，如下

让后分别进行差分，红色和橙色对应上面的链

等会，为什么非要是 $5\rightarrow 6$ 而不是 $2\rightarrow 6$ 呢？因为 $2\rightarrow 3$ 的路径已经将2已经加过了啊。

为什么我们用LCA呢，我们假设2种情况，第一种情况就是要加的树都在一个链上，这时候LCA就是深度最小节点的的父亲，例如对 $2\rightarrow 3$ 进行操作。第二种就是像上述 $3\rightarrow 6$ 拐过来，我们用LCA就可以求出这个路径的拐点，拐点就是 $LCA(3,6)=2$ 。让后像上面一样拆成2条链

让后跑一遍Dfs就可以统计出来答案啦。

例题P3128 [USACO15DEC] Max Flow P

其实就是上面的点差分经典例题

这里LCA我们使用的是倍增求LCA

小技巧：

__lg(x)

这个函数可以直接搞出来整数的 $log_2x$

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int n,m;
const int MN=5e4+15,ML=40;
int fa[MN][ML],dep[MN],ml,sum[MN],ans=-1;
vector<int> adj[MN];
void dfs(int u,int pre){
    fa[u][0]=pre;
    dep[u]=dep[pre]+1;
    for(int i=1;i<=ml;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(auto v:adj[u]){
        if(v!=pre){
            dfs(v,u);
        }
    }
}
int lca(int x,int y){
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    for(int i=ML-1;i>=0;i--){
        if(dep[fa[y][i]]>=dep[x]){
            y=fa[y][i];
        }
    }
    if(x==y) return x;
    for(int i=__lg(dep[x]);i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
void dfss(int u,int fa){
    for(auto v:adj[u]){
        if(v!=fa){
            dfss(v,u);
            sum[u]+=sum[v];
        }
    }
    ans=max(ans,sum[u]);
}
int main(){
    cin>>n>>m;
    ml=__lg(n);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    while (m--)
    {
        int s,t;
        cin>>s>>t;
        int l=lca(s,t);
        sum[s]++;
        sum[t]++;
        sum[l]--;
        if(l!=1){
            sum[fa[l][0]]--;
        }
    }
    dfss(1,0);
    cout<<ans;
    return 0;
}