树链剖分/重链剖分 学习笔记
A_man
·
2023-09-21 17:05:38
·
算法·理论
定义/解释
树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。
树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作「实链剖分」），大多数情况下（没有特别说明时），「树链剖分」都指「重链剖分」。
重链剖分可以将树上的任意一条路径划分成不超过log(n)条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。
重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。
(内容来自OI Wiki)
一些关于树链剖分的基础概念
重儿子：一个节点的所有儿子中子树最大的儿子
轻儿子：一个节点的所有儿子中除去重儿子之外的儿子
重边：一个节点与它重儿子的边
重链：由若干条重边组成的链
轻链：重链以外的链
总而言之，树链剖分的主要思想就是将树分割成若干条链，将其转换为线性结构，再使用各种不同的数据结构来维护树上路径的各种信息。
第一部分：如何分割
那既然叫重链剖分，肯定是通过重链来分割的。我们先通过定义来画一下重链：
（图中我们将重链标成了红色）
我们保留所有的重链，将剩下的边删去。
现在我们发现，这棵树被分割成了4条单独的链。那么这也就是树链剖分的分割过程。
也就是说，我们求出一棵树所有的重链，就能把这棵树分割开。 但是考虑到后面的维护操作，我们在分割的过程中不是仅仅求出重链即可，其实还要求很多其他的东西。
那么，让我们想想我们需要什么。
对于一条重链，我们需要知道它的链顶的节点，方便我们维护树上路径；我们还需要一个在重链上能够连续的新编号，因为我们肯定没法通过原来的编号对重链上的点进行操作；根据重链的定义，我们还必须求出每个节点的子树大小，不然我们就没办法找出节点的重儿子；另外，对于树上问题，求出一个节点的深度和父亲是必要的。
那么，总结一下我们需要的东西：
每个节点的深度，父亲
每个节点的子树大小
每个节点的重儿子
每条重链的链顶节点
一个新的连续的dfs序
然后我们就可以通过dfs来求这些内容了，在代码实现上，我们选择跑两遍dfs，第一遍求每个节点的深度、父亲、子树大小、重儿子；第二遍求重链的链顶节点和一个新的dfs序，同时依据题目维护必要的树上信息。
我们先来看第一个dfs
void dfs1(int x,int fa,int dep) //很经典的dfs
{
f[x]=fa;
depth[x]=dep;
sizes[x]=1;
for(int i=head[x];i!=-1;i=Next[i])
{
int y=ver[i];
if(y==fa) continue;
dfs1(y,x,dep+1);
sizes[x]+=sizes[y];
if(sizes[y]>sizes[hson[x]]) //sizes[0]=0 比较时不会出问题
{
hson[x]=y; //取子树大小最大的儿子为重儿子
}
}
}
其实除了求重儿子的部分，其他都是很简单的树上dfs
还是解释一下
f数组记录父亲 depth数组记录深度 sizes数组记录子树大小
hson数组记录每个节点的重儿子，在回溯时我们求出每个节点的子树大小，同时将节点的儿子中子树最大的儿子作为该节点的重儿子。
然后我们再看第二个dfs
void dfs2(int x,int t) //t表示 x所在重链的链顶
{
tops[x]=t; //链顶
dfn[x]=++idc; //dfs序
w[idc]=a[x]; //将原数组按dfs序映射到新数组上 方便线段树维护
if(hson[x]==0) return ;
dfs2(hson[x],t);
//优先遍历重儿子 保证重链编号连续 方便维护
for(int i=head[x];i!=-1;i=Next[i])
{
int y=ver[i];
if(y==f[x]||y==hson[x]) continue; //再往后我们只记录轻链
dfs2(y,y); //轻链的链顶就是它自己
}
}
注释还是比较详细的。
注意我们这里优先遍历重链的目的是使得每条重链上的dfs序是连续的，这样就方便我们后续用数据结构来维护重链上信息。
那么现在这棵树我们就分割完啦(^▽^)
第二部分：如何维护
嗯...等等，我们要维护什么？
当然是具体题目具体分析啦
举个例子，我们维护树上两点之间最短路径的权值和(带修改的)
我们考虑线段树维护
那么代码就长这样：
void Tree_path_update(int x,int y,int z) //修改路径上的点权
{
//最短路径的本质就是求LCA 我们在让x和y向LCA上跳的同时维护区间修改
while(tops[x]!=tops[y]) //如果说x和y不在同一条重链上 我们就上跳
{
if(depth[tops[x]] update(1,dfn[tops[x]],dfn[x],z); //在上跳前维护这个区间修改 注意区间左端点小于右端点 x=f[tops[x]]; //我们从x跳到它重链链顶的父亲 } //重复操作直到两者在同一条重链上 //其实此时两者不一定在同一个点上 所以再维护一次 (即使在一个点上 这个点也还没有修改) if(depth[x]>depth[y]) swap(x,y); //保证维护区间左端点小于右端点 update(1,dfn[x],dfn[y],z); } 我感觉代码注释挺详细的，我就不用再解释了 这里代码的本质还是维护重链，再用类似LCA的方法把路径连起来，此处注意一些细节： 上跳的时候是让重链链顶深度较大的点先跳(因为每次会跳到链顶的父亲)，这里一定是比较链顶的深度。 if(depth[tops[x]] 然后就是注意跳到同一条重链后两点不一定是同一点，还要再算一次。(线段树维护始终记得操作区间左端点小于等于右端点) 然后就完成啦！ 第三部分：如何查询 我是来凑数的awa 这其实是线段树的部分，操作和区间修改是一样的，这里仅给出代码: int Tree_path_query(int x,int y) //查询路径点权 操作同修改 不做解释 { int ans=0; while(tops[x]!=tops[y]) { if(depth[tops[x]] ans+=query(1,dfn[tops[x]],dfn[x])%p; x=f[tops[x]]; } if(depth[x]>depth[y]) swap(x,y); ans+=query(1,dfn[x],dfn[y])%p; return ans%p; } 第四部分：模板题 链接在这里 模板题的大部分内容前面已经讲完了，这里强调几点细节 这个题一定要取模 这里我们线段树维护的时候一定要注意，我们维护的是dfs之后重新编号的节点权值和，这一点在我们跑dfs时要重新建一个数组记录重新编号之后的点权，然后再建树 维护最短路径下权值和的操作前面已经给出，对于维护节点子树权值和的操作，我们直接进行线段树维护，因为一个点子树的编号是连续的。具体内容看代码 最后，给出模板题的详细注解AC代码 这里 ——END