基本概念
- 重子节点：所有子节点中子树大小最大的儿子节点
- 轻子节点：除重儿子之外的所有子节点
- 重边：重子节点和其父节点之间连的边
- 轻边：轻子节点和其父节点之间连的边
- 重链：重边连接而成的链
- dfs序：对树进行深度优先搜索，第一次访问到某个点时对其标号，按标号从小到大排序得到的序列叫dfs序
- dfs序是能够反映树上的点连续的信息的，所以链就是dfs序
树链剖分的优点
- 求LCA中的优化无非就是减少无效搜索的次数
- 树链剖分把树拆成不同的链（保证不重不漏）
- 因为两个点的LCA一定在一条链上（同一个点）
- 所以如果搜索到的点不在同一条链上，那么不是倍增跳或是······，而是跳过一整条链
- 这样搜索的速度会大幅提高
- 我们知道，在dfs序里，许多点分成了好多段
- 比如这里有一棵树：我们假设它的dfs序为:abdhiejcfg
- 那么对于一条路径a-h，它的dfs序是连续的
- 如果我们要更改他们的信息，我们就很好的利用了线段树区间修改的优点
- 但如果我们要更改i-g的信息，我们发现这条路径 i-d-b-a-c-g 在dfs序中并不连续，甚至在这里我们必须单点修改
- 完全没有发挥线段树区间维护的优势
- 在这里我们得到了一个启示：
- 我们尽量要让尽可能多的点在dfs序中连续
- 这样我们修改时才会尽可能地发挥线段树区间维护的优势
- 很明显，我们可以做到划分
- 这个就是重儿子轻儿子的概念
- 重儿子：以该儿子为根的子树所含节点数是其他儿子中最多的
- 轻儿子：除重儿子之外就是轻儿子
- 所以我们在DFS中，优先搜索重儿子，这样，我们就能让更多的节点在dfs序中连续
为什么讲树链剖分求LCA
- 因为链上修改是基于求LCA操作的
- 相比于树链剖分求LCA，链上修改只是加了个线段树的操作而已
- 关于LCA
- 我们运用top[i]表示i所在重链链的深度最浅的节点编号
- 对于轻链上的点i的top[i]就是它本身i同时用id[i]表示i节点在dfs序中的位置
- 这样，id[top[i]]~id[i]的区间就是一条链上的点了
- 如top[11]-11点在dfs序上是连续的
- 于是我们可以直接修改这一段区间的信息，都让它们加1
一般来讲，树链剖分可以解决以下问题
- 1.修改两点路径上各点的值
- 2.查询两点路径上各点的值
- 3.修改某点子树上各点的值
- 4.查询某点子树上各点的值
- 5.求解LCA问题
树上修改/查询
- 以某一个节点为根的子树编号是这个节点+这个节点的size[]-1
- 即新树映射到数列上，一棵子树所占的区间是：[id[x],id[x]+size[x]−1]
正文
- 例题及注释
- 重链剖分的代码可以概括为：DFS+线段树+LCA
- DFS是为了处理信息
- 线段树和LCA是为了解决问题
- 首先进行2次DFS进行初始化
- 先看DFS1
- 第一次，我们处理出重儿子和其他易于统计的信息
- 第二次，我们按照重儿子优先的原则去dfs并记下dfs序和节点编号的对应关系，顺便处理链上信息
- 至此我们就处理完了所有需要的信息，成功剖树为链
- 然后上线段树
- 然后看DFS2，每个点遍历子节点时优先遍历的是重儿子
- 这说明每条重链的dfs序上的位置是连续的一段
- 而每一次在树上移动是直接移动到链头
- 这就可以对这一条重链上的信息区间修改或者查询
- 直接把dfs序架在线段树上就能实现了
- 通过爬lca时每次跳链头来区间修改或查询就完成了
