树上差分

· · 算法·理论

前置知识：树上倍增求 LCA。

点差分

以 P3128 为模板题讲解。

考虑差分思想。如何在树上做差分？

我们可以定义一个数组 c，c_i 表示结点 i 到根结点这条链上的所有结点 +1。

假设现在要给 l 到 r 这条链上的所有结点 +1，如果只是单纯 c[l]++,c[r]++ 的话，会出现下图的情况。

与预期不符，l 和 r 的 \text{LCA} 本应算一次，却算了两次，\text{LCA} 的所有祖先结点都应不算，却都算了 2 次。

根据这个点可以得出，我们可以修改成下面这样解决这个问题：

c[l]++,c[r]++;
c[lca(l,r)]--,c[lca(l,r)的父亲]--;

接下来差分完毕后考虑求解答案。由于 c_i 表示结点 i 到根结点这条链上的所有结点 +1，所以求每个结点的数可以用递归，遍历并将每个结点的所有子节点的 c_i 相加，就可以得到答案了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e4+100,LG=30,M=1e5+100;
int n,m,t[N],k,deep[N],st[N][LG],x,y,lg[N],c[N],b[N],ma,qs,qt;
bool flag[N]; 
struct node
{
    int id,last;
}a[M*2];
void add(int a1,int a2)
{
    a[++k].id=a2; 
    a[k].last=t[a1];
    t[a1]=k;
}
void dfs(int dx,int fa)
{
    deep[dx]=deep[fa]+1;
    st[dx][0]=fa;
    for(int i=t[dx];i;i=a[i].last)
    {
        if(a[i].id!=fa&&!deep[a[i].id]) dfs(a[i].id,dx);
    }
}
int lca(int dx,int dy)
{
    if(deep[dx]<deep[dy]) swap(dx,dy);
    for(int i=lg[n];i>=0;i--)
    {
        if(deep[st[dx][i]]>=deep[dy]) dx=st[dx][i]; 
        if(dx==dy) return dx;
    }
    for(int i=lg[n];i>=0;i--)
    {
        if(st[dx][i]!=st[dy][i]) dx=st[dx][i],dy=st[dy][i];
    } 
    return st[dx][0];
}
void update(int dx,int dy)
{
     c[dx]++,c[dy]++;
     c[lca(dx,dy)]--,c[st[lca(dx,dy)][0]]--;
}
void ans(int dx)
{
    flag[dx]=true;
    b[dx]=c[dx];
    for(int i=t[dx];i;i=a[i].last)
    {
        if(a[i].id!=st[dx][0]&&!flag[a[i].id]) 
        {
            ans(a[i].id);
            b[dx]+=b[a[i].id];
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=lg[n];i++)
    {
        for(int j=1;j<=n;j++) st[j][i]=st[st[j][i-1]][i-1];
    }
    for(int i=1;i<=m;i++) 
    {
        scanf("%d%d",&qs,&qt);
        update(qs,qt);
    }
    ans(1);
    for(int i=1;i<=n;i++) ma=max(ma,b[i]);
    printf("%d",ma);
    return 0;
}

边差分

找不到模板题就先不放了。