Part.1 引入
重链剖分是一种用于解决树上的路径查询和修改问题的算法，他能将 \(O(n)\) 级别的操作转换为 \(O(\log n)\) 的级别，可以说十分常用。本文将带你深入解析这个算法。
Part.2 概念和思路
在讲解本算法之前，我们先引入一些概念：
- 轻重儿子：对于一个树上的节点 \(u\)，其儿子中子树大小最大的叫重儿子，其余的叫轻儿子。为了方便理解，我们把根节点算作轻儿子；
- 轻重边：对于一个树上的节点 \(u\)，连向重儿子的边叫重边，否则就是轻边；
- 重链：从一个轻儿子出发，一直向深处走重边，形成的路径叫做重链。
如上图所示，红色的节点代表重儿子，绿色的节点代表轻儿子，蓝色的方框是一条重链。
由于每个点只有一个重儿子，按照重链一定能把树分成若干个不重不漏的部分。这种算法就叫做重链剖分。
重链剖分有个很好的性质，就是从任意一个点出发向根走，至多经过 \(\log n\) 条轻边，也就是至多经过 \(\log n\) 条重链。因为对于一个节点 \(u\)，其重儿子的子树大小一定大于其轻儿子的子树大小，那么意味着从 \(u\) 的任何一个轻儿子跳到 \(u\)，子树大小都会乘 \(2\)。
那我们如何去实现这个算法呢？
最普遍的就是两边 DFS 法。首先第一遍 DFS 需要确认一个节点的父亲、深度、子树大小、重儿子等信息，第二遍 DFS 确认每个节点所在重链的链顶。如果需要，在第二遍 DFS 中还要确定 DFS 序等信息。
Part.3 代码实现
如果没有搞懂上面在说啥，可以配合代码理解：
int son[N],top[N],f[N],siz[N],dep[N],dfn[N],pre[N],idx;
vector<int> g[N];
void dfs1(int u,int fa)
{
f[u] = fa,dep[u] = dep[fa]+1,siz[u] = 1;//确定父亲、深度
for(auto v:g[u])
{
if(v==fa) continue;
dfs1(v,u),siz[u]+=siz[v];//确定子树大小
if(siz[son[u]]<siz[v]||son[u]==0) son[u] = v;//确定重儿子
}
}
void dfs2(int u,int tp)//tp就是当前节点所在重链的链顶
{
dfn[u] = ++idx,top[u] = tp,pre[idx] = u;//DFS序，链顶
if(son[u]==0) return;//连重儿子都没有，怎么可能有儿子
dfs2(son[u],tp);//往重儿子走，链顶不变
for(auto v:g[u])
{
if(v==f[u]||v==son[u]) continue;
dfs2(v,v);//往轻儿子走，形成新的重链
}
}
Part.4 应用
上面的对解题没啥大用，接下来，正片开始。
1.树剖求 LCA
树剖求 LCA 其实是一个非常经典的应用。我们从两个节点出发，每次选一个点，跳到他所在链顶的父亲节点上，知道两个点在同一条重链为之。那关键是我们选那个点呢？总不能随机数吧。
我们可以发现，深度越小（即越靠近树根）的点越容易成为 LCA，所以每次我们选一个链顶深度大的节点开始跳。这样，我们就能保证正确性了。
当两个点在同一条重链是，深度小的就是 LCA，返回即可。代码如下：
int lca(int x,int y)
{
while(top[x]!=top[y])//不在一条链上
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳链顶深度大的点
x = f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);//返回深度小的点
return x;
}
2.树剖维护路径、子树信息
其实和求 LCA 的区别不大。再求 LCA 的过程中，我们把路径上的点拆成若干条重链。而在一条重链上，节点的 DFS 序是连续的。所以考虑对 DFS 序建立数据结构（比如线段树）。
至于维护子树信息，是一样的，因为子树内 DFS 序也是一段连续的区间。
具体的，我们来看看 P3384 怎么实现。
#include <bits/stdc++.h>
#define int long long //开个 long long
#define ls (k*2)
#define rs (k*2+1)
using namespace std;
//快读快写
template<typename T> inline void read(T &x)
{
x = 0;
T f = 1;char ch = getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
f = -1,ch = getchar();
break;
}
ch = getchar();
}
while(ch>='0'&&ch<='9')
x = (x<<3)+(x<<1)+ch-48,ch = getchar();
x*=f;
}
template<typename T> inline T read()
{
T x;read(x);return x;
}
template<typename T> inline void write(T x)
{
if(x<0) x = -x,putchar('-');
if(x<=9) return putchar(x+48),void();
write(x/10);
putchar(x%10+48);
}
template<typename T> inline void writen(T x)
{
write(x);
puts("");
}
const int N = 1e5+5;
int n,q,mod,rt;
int son[N],top[N],f[N],siz[N],dep[N],dfn[N],pre[N],w[N],idx;
vector<int> g[N];
//区间加、区间求和线段树板子
struct node{
int val,tag;
friend node operator + (node x,node y)
{
node res;
res.val = (x.val+y.val)%mod;
res.tag = 0;
return res;
}
}t[N*4];
void pushup(int k)
{
t[k] = t[ls]+t[rs];
}
void down(int k,int l,int r,int mid)
{
if(!t[k].tag) return;
(t[ls].val+=t[k].tag*(mid-l+1))%=mod,(t[rs].val+=t[k].tag*(r-mid))%=mod;
(t[ls].tag+=t[k].tag)%=mod,(t[rs].tag+=t[k].tag)%=mod;
t[k].tag = 0;
}
void build(int k,int l,int r)
{
if(l==r)
{
t[k].val = w[pre[l]];
return;
}
int mid = (l+r)/2;
build(ls,l,mid),build(rs,mid+1,r);
pushup(k);
}
void change(int k,int l,int r,int x,int y,int v)
{
if(l>y||r<x) return;
if(l>=x&&r<=y)
{
t[k].val+=v*(r-l+1),t[k].tag+=v;
return;
}
int mid = (l+r)/2;
down(k,l,r,mid);
change(ls,l,mid,x,y,v),change(rs,mid+1,r,x,y,v);
pushup(k);
}
int ask(int k,int l,int r,int x,int y)
{
if(l>y||r<x) return 0;
if(l>=x&&r<=y) return t[k].val;
int mid = (l+r)/2;
down(k,l,r,mid);
return ask(ls,l,mid,x,y)+ask(rs,mid+1,r,x,y);
}
//重链剖分
void dfs1(int u,int fa)
{
f[u] = fa,dep[u] = dep[fa]+1,siz[u] = 1;//确定父亲、深度
for(auto v:g[u])
{
if(v==fa) continue;
dfs1(v,u),siz[u]+=siz[v];//确定子树大小
if(siz[son[u]]<siz[v]||son[u]==0) son[u] = v;//确定重儿子
}
}
void dfs2(int u,int tp)//tp就是当前节点所在重链的链顶
{
dfn[u] = ++idx,top[u] = tp,pre[idx] = u;//DFS序，链顶
if(son[u]==0) return;//连重儿子都没有，怎么可能有儿子
dfs2(son[u],tp);//往重儿子走，链顶不变
for(auto v:g[u])
{
if(v==f[u]||v==son[u]) continue;
dfs2(v,v);//往轻儿子走，形成新的重链
}
}
void changetree(int x,int y,int v)
{
v%=mod;
while(top[x]!=top[y])//不在一条链上
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳链顶深度大的点
change(1,1,n,dfn[top[x]],dfn[x],v),x = f[top[x]];//修改一整个重链
}
if(dep[x]>dep[y]) swap(x,y);//深度小的点为 LCA
change(1,1,n,dfn[x],dfn[y],v);//修改最后重链的一部分
}
int asktree(int x,int y)
{
int res = 0;
while(top[x]!=top[y])//不在一条链上
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);//跳链顶深度大的点
(res+=ask(1,1,n,dfn[top[x]],dfn[x]))%=mod,x = f[top[x]];//查询一整个重链
}
if(dep[x]>dep[y]) swap(x,y);//深度小的点为 LCA
(res+=ask(1,1,n,dfn[x],dfn[y]))%=mod;//查询最后重链的一部分
return res;
}
//主函数
signed main()
{
read(n),read(q),read(rt),read(mod);
for(int i = 1;i<=n;i++)
read(w[i]);
for(int i = 1,u,v;i<n;i++)
read(u),read(v),g[u].push_back(v),g[v].push_back(u);
dfs1(rt,0),dfs2(rt,rt);
build(1,1,n);
while(q--)
{
int op,x,y,z;
read(op),read(x);
if(op==1)
{
read(y),read(z);
changetree(x,y,z);
}
else if(op==2)
{
read(y);
writen(asktree(x,y)%mod);
}
else if(op==3) read(y),change(1,1,n,dfn[x],dfn[x]+siz[x]-1,y%mod);
else writen(ask(1,1,n,dfn[x],dfn[x]+siz[x]-1)%mod);
}
return 0;
}
讲完啦！码字不易，给个赞吧！
\[\text {THE END} \] 标签：剖分,int,void,笔记,tag,重链,节点,mod From： https://www.cnblogs.com/pyy51316/p/18121637