树链剖分 算法学习
树你应该懂的吧o( ̄︶ ̄)o 学习树链剖分之前需要先学习:$dfs$、线段树(当然大佬们用树状数组代替线段树也可以O(∩_∩)O),据说一名普及+的$oier$应该都会呀

先来了解树链剖分的用处

Luogu题目传送门 已知一棵包含$N$个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:
  • 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
  • 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
  • 操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z
  • 操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和
如果直接暴力的话,肯定会TLE(废话)。所以这时候,树链剖分闪亮登场。

什么是树链剖分

一种算法(废话),它通过分轻重边把树分割成很多链,然后利用某种数据结构维护这些链(比如上文提到的线段树、树状数组等)但前提是这种数据结构支持动态修改(你别给我整个RMQ)。本质上是一种暴力算法。 PS:树剖的复杂度约为$O(nlog^2n)$

树链剖分的基本概念

名称概念
重儿子父亲节点的所有儿子中子节点数目最多(sz最大)的节点
轻儿子父亲节点除了重儿子以外的儿子
重边父亲节点和重儿子连成的边
轻边父亲节点和轻儿子连成的边
重链由多条重边连成的路径
轻链由多条轻边连成的路径
没看懂?没关系,结合下面这张图:(红色的边代表重边,黑色的边代表轻边,红色的节点代表重儿子,黑色的节点代表轻儿子) PS:这里默认树根也是重儿子。
上图的重链有:1-4,3-6。

变量声明

名称作用
$fir_x$关于$x$的最后一条边编号
$nxt_x$关于$x$的上一条边编号
$son_x$第$x$条边的连向
$w_x$其实没啥用,打着习惯了
$a_x.ls$编号为$x$的节点的左儿子
$a_x.rs$编号为$x$的节点的右儿子
$fa_x$编号为$x$的节点的父亲
$c_x$编号为$x$的节点的重儿子
$rk_x$当前$dfs$标号在树中所对应的节点的编号
$top_x$编号为$x$的节点所在链的顶端节点编号
$id_x$编号为$x$的节点$dfs$后的新编号
$dep_x$编号为$x$的节点的深度
$sz_x$以编号为$x$的节点为根的子树的节点个数

树链剖分的实现

第一次$dfs$求出每个节点的重儿子、父亲、深度、子树大小。

PS:如果一个点的多个儿子所在子树大小相等且最大,那随便找一个当做它的重儿子就好了,叶节点没有重儿子,非叶节点有且只有一个重儿子。 操作完以后应该是下图:

第二次$dfs$求出每个节点的链顶端节点、新编号、$dfs$编号对应的节点编号。

操作完以后应该是下图:

线段树等数据结构的维护

接下来就是线段树、树状数组等数据结构的维护了,具体使用哪种数据结构因题目而异,这里提供模板题(上文介绍的题目)所使用的线段树(区间修改、区间询问)。

根据题目需要添加操作

就比如上文的题目中还要求的操作:
  • 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
  • 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
与操作3、操作4不同,这里要求的是一条路径上的节点,而没有告诉我们节点的编号,所以,我们这时要求出节点编号: 当然,还有一个操作是非常常用的,那就是求lca(最近公共祖先)。

模板题代码

对对对,就是上文提到的题目。 完美撒花✿✿ヽ(°▽°)ノ✿
暂无评论

发送评论


				
上一篇
下一篇