一些概念

在学习重链剖分前，首先要明白以下几个概念：

中二重儿子：就是一个节点的儿子中最“重”的那个，“重”表示的是子树大小最大，如果都一样大，就随便选一个就好了（用 $son$ 数组存储）
亲轻儿子：除了重儿子外其他的儿子
重边：重儿子和父亲之间的边
轻边：轻儿子和父亲之间的边
重链：重边连在一起形成的链
轻链：轻边连在一起形成的链（貌似没啥用）
重链顶点：一条重链中，深度最小的点（用 $top$ 数组记录）

为了方便大家理解，这里我画了一张图，来表示重链剖分后的结果：

其中，红色的线表示重边，连在一起，形成 $3$ 条重链；黑色的线表示轻边，连在一起，形成 $3$ 条轻链
这样，大家对这些概念应该都了解了吧？

算法讲解

接下来，我们来介绍如何进行重链剖分
首先，我们进行第一遍dfs，求出子树的大小（ $siz$ ），重儿子（ $son$ ），父亲节点（ $fa$ ）和每个点的深度（ $dep$ ）
$size$ 、 $fa$ 和 $dep$ 的求法就不用说了吧……
我们来讲讲 $son$ 的求法
首先，设一个变量 $maxson$ ，初值为 $-1$ ，记录最大的子树大小
接着，对于枚举的每棵子树，假设当前枚举的子树的根为 $v$ ，判断 $maxson$ 和 $siz[v]$ 的大小
如果 $siz[v]>maxson$ ，那么 $son[u]=v$
代码：

int dfs1(int x,int Fa,int Dep)
{
    dep[x]=Dep,fa[x]=Fa,siz[x]=1;
    int maxson=-1;
    for(int i=head[x];i!=-1;i=e[i].nxt) if(e[i].v!=Fa){
        siz[x]+=dfs1(e[i].v,x,Dep+1);
        if(siz[e[i].v]>maxson) maxson=siz[e[i].v],son[x]=e[i].v;
    }
    return siz[x];
}

接着，我们来讲一讲第二个dfs，这个dfs要求出dfs序（

$dfn$ ）和重链顶点（

$top$ ）
为了方便，我们首先先遍历重儿子，再遍历其他轻儿子，重儿子的重链顶点和该节点的重链顶点相同，轻儿子的重链顶点是自己
至于方便在什么地方，后面再说
代码：

void dfs2(int x,int Top)
{
    dfn[x]=++cnt,top[x]=Top;
    if(!son[x]) return;
    dfs2(son[x],Top);
    for(int i=head[x];i!=-1;i=e[i].nxt) if(!dfn[e[i].v]) dfs2(e[i].v,e[i].v);
}

这样，我们就完成了重链剖分的全过程

应用

那么，剖分完后又有什么好处呢？

求最近公共祖先

~~众所周知，~~有一种求最近公共祖先（LCA）的算法，使用的是倍增，这个算法预处理是 $\Theta(nlogn)$ 的，单次询问是 $\Theta(logn)$ 的
有比这个更快的算法吗？有！用重链剖分解决！
等等，这和重链剖分有什么关系呢？最近公共祖先和这两个点所在的重链也不一定一样啊，这怎么做呢？
别急，马上大家就会理解了
我们以下面这张图为例，求两个蓝色的点的最近公共祖先

模仿倍增法求LCA，我们就很容易理解重链剖分求LCA的方法了
我们只需要选择深度较深的点，不断向上跳到重链的顶端即可
首先，蓝色的点调到重链顶端（绿点），然后再向上跳一条边（黄点），这样就转换到了另外一条重链上
最后，当两个点在同一条重链上时，深度较小的那个点就是他们的最近公共祖先了
那么，重链剖分求LCA时，预处理为 $\Theta(n)$ ，单次询问为 $\Theta(logn)$
完整代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct ppap
{
    int u,v,nxt;
}e[2000010];
int n,m,root,tot,cnt,head[2000010],dep[2000010],fa[2000010],son[2000010],siz[2000010],top[2000010],dfn[2000010];
void add(int x,int y)
{
    e[++tot].nxt=head[x],head[x]=tot,e[tot].u=x,e[tot].v=y;
}
int dfs1(int x,int Fa,int Dep)
{
    dep[x]=Dep,fa[x]=Fa,siz[x]=1;
    int maxson=-1;
    for(int i=head[x];i!=-1;i=e[i].nxt) if(e[i].v!=Fa){
        siz[x]+=dfs1(e[i].v,x,Dep+1);
        if(siz[e[i].v]>maxson) maxson=siz[e[i].v],son[x]=e[i].v;
    }
    return siz[x];
}
void dfs2(int x,int Top)
{
    dfn[x]=++cnt,top[x]=Top;
    if(!son[x]) return;
    dfs2(son[x],Top);
    for(int i=head[x];i!=-1;i=e[i].nxt) if(!dfn[e[i].v]) dfs2(e[i].v,e[i].v);
}
int LCA(int x,int y)
{
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) return y;
    return x;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m>>root;
    for(int i=1,x,y;i<=n-1;i++) cin>>x>>y,add(x,y),add(y,x);
    dfs1(root,0,1),dfs2(root,root);
    while(m--){
        int x,y;
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
}

对树上的一条链进行修改和查询

重链剖分还有什么作用呢？
它可以对树上的任意一条链进行修改
以下图为例，我们假设每个点有一个点权，我们要让两个蓝点之间的链上的每个点的权 $+1$ （包括两个蓝点），怎么操作呢？

首先，对于这种相连的东西一起修改的题目，我们很容易就会想到线段树
在树上建线段树，用的一定就是dfs序了
还记得我们前面遍历每个节点的子节点时，是先遍历它的重儿子吗？
当时我说这是为了方便
是的，就是在建线段树和计算时更方便了！
因为所有重链上的点的dfs序一定是连续的，这样，一条重链上的点的值修改只需要进行简单的线段树上区间修改即可
所以我们考虑把链划分成许多个重链相连（如下图）

那么，我们就可以分别修改每一段的值，查询时也一样，分别查询每一段的值，然后再加在一起即可
对于这个链的划分操作，和LCA的求法类似，只需要不断地跳到重链顶点的父亲节点，就可以了
模板题代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct ppap
{
    int u,v,nxt;
}e[2000010];
struct Segment_Tree
{
    int l,r,sum,siz,add;
}t[2000010];
int n,m,root,MOD,tot,cnt,a[2000010],b[2000010],head[2000010],dep[2000010],fa[2000010],son[2000010],siz[2000010],top[2000010],dfn[2000010];
void add(int x,int y)
{
    e[++tot].nxt=head[x],head[x]=tot,e[tot].u=x,e[tot].v=y;
}
int dfs1(int x,int Fa,int Dep)
{
    dep[x]=Dep,fa[x]=Fa,siz[x]=1;
    int maxson=-1;
    for(int i=head[x];i!=-1;i=e[i].nxt) if(e[i].v!=Fa){
        siz[x]+=dfs1(e[i].v,x,Dep+1);
        if(siz[e[i].v]>maxson) maxson=siz[e[i].v],son[x]=e[i].v;
    }
    return siz[x];
}
void dfs2(int x,int Top)
{
    dfn[x]=++cnt,a[cnt]=b[x],top[x]=Top;
    if(!son[x]) return;
    dfs2(son[x],Top);
    for(int i=head[x];i!=-1;i=e[i].nxt) if(!dfn[e[i].v]) dfs2(e[i].v,e[i].v);
}
void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r,t[p].siz=r-l+1;
    if(l==r){t[p].sum=a[l];return;}
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum+MOD)%MOD;
}
void spread(int p)
{
    if(t[p].add){
    	t[p*2].sum=(t[p*2].sum+t[p*2].siz*t[p].add)%MOD;
    	t[p*2+1].sum=(t[p*2+1].sum+t[p*2+1].siz*t[p].add)%MOD;
    	t[p*2].add=(t[p*2].add+t[p].add)%MOD;
    	t[p*2+1].add=(t[p*2+1].add+t[p].add)%MOD;
    	t[p].add=0;
    }
}
void change(int p,int l,int r,int d)
{
    if(l<=t[p].l&&t[p].r<=r){t[p].sum+=t[p].siz*d,t[p].add+=d;return;}
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    t[p].sum=(t[p*2].sum+t[p*2+1].sum+MOD)%MOD;
}
int ask(int p,int l,int r)
{
    int ans=0;
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) ans=(ans+ask(p*2,l,r))%MOD;
    if(r>mid)  ans=(ans+ask(p*2+1,l,r))%MOD;
    return ans;
}
void modify(int x,int y,int d)
{
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,dfn[top[x]],dfn[x],d);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    change(1,dfn[x],dfn[y],d);
}
void query(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=(ans+ask(1,dfn[top[x]],dfn[x]))%MOD;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=(ans+ask(1,dfn[x],dfn[y]))%MOD;
    cout<<ans<<endl;
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n>>m>>root>>MOD;
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1,x,y;i<=n-1;i++) cin>>x>>y,add(x,y),add(y,x);
    dfs1(root,0,1),dfs2(root,root),build(1,1,n);
    while(m--){
        int op,x,y,z;
        cin>>op;
        if(op==1) cin>>x>>y>>z,z%=MOD,modify(x,y,z);
        else if(op==2) cin>>x>>y,query(x,y);
        else if(op==3) cin>>x>>z,change(1,dfn[x],dfn[x]+siz[x]-1,z%MOD);
        else if(op==4) cin>>x,cout<<ask(1,dfn[x],dfn[x]+siz[x]-1)<<endl;
    }
}

树链剖分之重链剖分详解

一些概念

算法讲解

应用

求最近公共祖先

对树上的一条链进行修改和查询

相关练习题