前言
打算好好写一篇文章。
至于为什么选了树剖这个主题，一是因为不久前学了长剖求树上 k 级祖先，二是因为重剖是我进提前批以来第一个学习到的树上算法，再加上有学弟写的超级详细的树剖学习笔记，也会使我写起来比较轻松一点。
同时也可以熟悉一下 TikZ 这个宏包，它的功能实在是太多了，画出来的图也很美观，个人很喜欢这种风格。
0. 树链剖分的思想和应用
树剖可以将树按不同的方式分割成若干条链的组合，多用于维护树上路径的信息。
进行树剖之后，由于一些性质（比如 dfs 序连续），我们通常使用一些数据结构来维护信息。
常见的树链剖分方式有：重（zhòng）链剖分，长链剖分和实链剖分等，在没有特别说明的情况下，树链剖分一般指重链剖分。
其中，重链剖分可以将树上的任意一条路径划分成不超过 \(\mathcal{O}(\log n)\) 条连续的链，而且能保证划分出的每条链上的节点 dfs 序连续，因此可以方便地用一些维护序列的数据结构（比如线段树）来维护树上路径的信息。
长链剖分的性质则没有那么优美，只能将路径划分成 \(\mathcal{O}(\sqrt{n})\) 条链，但由于它是按照节点深度进行剖分，所以在一些与深度有关的方面（比如树上 k 级祖先，有一维状态为深度维的树形 dp），能够有较优的复杂度。
而实链剖分多用于 LCT，较为灵活，一般使用 Splay 来维护剖出来的链。
在某些题目中，还可以利用其性质来灵活地运用树剖，具体用法视题目而定。
1. 重链剖分
常见剖分的一种，它按照子树大小对树进行划分，保证了其良好的复杂度。
1.1 相关定义
定义一个节点的重子节点为其子节点中子树大小最大的那个节点，如果有多个就任取其一，如果没有子节点就没有重子节点。
定义一个节点的轻子节点为除重子节点以外的其他子节点。
从一个节点到其重子节点的边叫做重边，从一个节点到其轻子节点的边叫做轻边。
多条重边首尾相连形成的链叫做重链。
下图展示了一棵树的重链剖分，其中红色的边表示重边。
1.2 性质
-
将孤立点也看做一条重链，则每个节点都属于一条重链。
-
所有重链将整棵树完全剖分。
-
从根出发到一个节点最多只会经过 \(\mathcal{O}(\log n)\) 条轻边，最多只会经过 \(\mathcal{O}(\log n)\) 条重链。
-
dfs 整棵树时，我们优先访问一个节点的重儿子，则这样遍历一遍得到的 dfs 序中，每条重链的 dfs 序总是连续的。
性质 3 的证明：考虑从根往下走，每经过一条轻边，所在子树大小至少会除以二（否则该子节点将会成为重子节点），于是轻边条数和重链个数都是 \(\mathcal{O}(\log n)\) 的。
1.3 算法流程
我们对整棵树进行两次 dfs。
第一次 dfs 时，我们计算出每个节点子树的大小，深度，父亲等有关信息，接着可以根据子节点子树大小找出重子节点。
第二次 dfs 时，我们记录每个节点的 dfs 序（\(\text{dfn}\)），以及链顶的编号（\(\text{top}\)），有时候需要额外记录一个 \(\text{rnk}_i\) 表示 dfs 序为 \(i\) 的节点编号。
注意在第二次 dfs 时我们优先访问重子节点，这样才能保证每条重链的 dfs 序连续。
1.4 代码实现
int timer;
int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N];
void dfs1(int u, int f) {
dep[u] = dep[f] + 1;
fa[u] = f; siz[u] = 1;
for (auto v : G[u]) {
if (v == f) continue;
dfs1(v, u); siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
rnk[dfn[u] = ++timer] = u;
top[u] = tp;
if (son[u]) dfs2(son[u], tp);
for (auto v : G[u]) {
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
因为 son[u] 的初值为 \(0\)，上述代码仅适用于节点编号从 \(1\) 开始的情况，若编号从 \(0\) 开始稍加修改即可。
1.5 应用
1.5.1 最近公共祖先（LCA）
求 LCA 是重链剖分最核心的功能，可以说所有维护路径信息的操作都基于这一个功能。
在朴素的倍增求法中，我们通过将两个节点倍增跳父亲的方式可以 \(\mathcal{O}(\log n)\) 的求出两个点的 LCA。
而根据重链剖分的性质，两个点之间的路径上只有 \(\mathcal{O}(\log n)\) 条重链，如果我们能在重链上快速移动，那么求 LCA 的复杂度就是 \(\mathcal{O}(\log n)\) 的。
具体来说：
-
若给定的两个节点在同一条重链上，则答案即为深度较小的那个节点。
-
否则我们找到两个节点所在重链的链顶深度较大的那个点，将其跳到所在重链链顶的父亲上。重复这个步骤直至两节点在同一重链上。
为什么要比较两个点所在重链的链顶的深度而不是只比较两个点的深度呢？考虑以下情况：
假设要求 \(\text{LCA}(5, 6)\)，此时如果先跳节点深度大的节点 \(6\)，我们就会将其跳到最顶上，从而错过原来的答案节点 \(2\)，而先跳所在重链的链顶的深度较大的节点 \(5\) 则不会出现以上问题。
我们再用几张图来说明整个算法的流程：
假设我们要求 \(\text{LCA}(9, 13)\)，由于节点 \(13\) 所在重链链顶（节点 \(11\)）的深度大于节点 \(9\) 所在重链链顶（节点 \(3\)）的深度，所以我们先将节点 \(13\) 往上跳到其链顶的父亲节点 \(8\)。
接着我们比较节点 \(8\) 和节点 \(9\) 所在重链链顶的深度大小，由于节点 \(9\) 所在重链链顶（节点 \(3\)）的深度大于节点 \(8\) 所在重链链顶（节点 \(1\)）的深度，所以我们将节点 \(9\) 往上跳到其链顶的父亲节点 \(1\)。
此时我们发现，节点 \(1\) 和节点 \(8\) 已经在同一条重链上，所以 \(\text{LCA}(9, 13) = 1\)。
代码实现
int LCA(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[u]]) std::swap(u, v);
u = fa[top[u]];
}
return (dep[u] < dep[v] ? u : v);
}
由于两点路径间的重链个数是 \(\mathcal{O}(\log n)\) 的，而我们每次向上跳一条重链的复杂度是 \(\mathcal{O}(1)\) 的，故总时间复杂度为 \(\mathcal{O}(\log n)\) 。
通常两点间的重链个数不会达到 \(\log n\) 这个上界，而倍增求 LCA 的跳父亲次数是严格 \(\log n\) 的，所以重链剖分求 LCA 的常数显著小于倍增求 LCA 的常数。
1.5.2 维护树上路径信息
首先我们考虑子树信息是怎么维护的，根据 dfs 的过程 ，一个节点子树内的所有节点的 dfs 序形成了一段连续区间 \([\text{dfn}_u, \text{dfn}_u + \text{siz}_u - 1]\)，于是我们就可以将子树修改转为区间修改，使用树状数组或线段树这些维护区间信息的数据结构来维护。
而根据重链剖分的性质，每条重链上的 dfs 序是连续的，这启发我们将路径上的点拆分成若干条重链进行维护。
考虑图中这条 \(6 \rightarrow 7\) 的路径，我们发现它恰好被分成了三条重链，而且这三条重链就是我们在跳 LCA 中所经过的三条！
于是我们可以在跳 LCA 的时候，对路径上的重链进行修改，其对应区间即为 \([\text{dfn}_{\text{top}_u}, \text{dfn}_u]\)。假设对区间操作的时间为 \(T(n)\)，由于重链条数为 \(\mathcal{O}(\log n)\)，我们可以在单次 \(\mathcal{O}(T(n)\log n)\) 的复杂度内维护树上路径信息。
不要忘记最后当 \(u\) 和 \(v\) 在同一条重链的时候也要进行操作。
代码实现
若操作为树上路径加，路径权值和查询，可能的代码如下：
SegTree<int> tree;
void modify(int u, int v, int k) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
tree.modify(1, 1, n, dfn[top[u]], dfn[u], k);
u = fa[top[u]];
}
if (dep[u] > dep[u]) std::swap(u, v);
tree.modify(1, 1, n, dfn[u], dfn[v], k);
}
int query(int u, int v) {
int ret = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
ret += tree.query(1, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if (dep[u] > dep[u]) std::swap(u, v);
return ret += tree.query(1, 1, n, dfn[u], dfn[v]);
}
大多数的重剖题目都是上面两者的应用，再根据题目的性质，套用不同的数据结构。说白了，重剖就是一个用于将树上路径转化到序列上维护的工具罢了。
1.6 例题
这里只讲一些经典模型和 trick。
1.6.1 边转点
对于有些题目，我们要维护的信息是在边上而不是在点上，而重剖是对点进行划分，不是很好维护。
由于一棵树有 \(n\) 个节点而只有 \(n - 1\) 条边，我们可以将每条边上的信息下放到位于它下部的点上，这样就能保证每个点只对应一条边的信息（除根节点外）。
这样子就可以使用维护点信息的方法来维护边信息，注意在 LCA 处的点是取不到的，在最后进行操作的时候要注意。
几道题目（都是要维护的信息在边上）：
P4114 Qtree1 | 单点修改 / 路径查询最大值。
P4315 月下“毛景树” | 路径修改 / 查询最大值。
P1505 [国家集训队] 旅游 | 单点修改，路径权值取相反数 / 路径查询和，最大值，最小值。
边转点和重链剖分之后就都是序列上的问题了，套用不同的线段树板子即可。
1.6.2 使用点权 / 边权维护重叠处信息
具体来说，有时候题目并不要求我们维护树上路径加 / 查询这些偏数据结构的操作，此时经过一些小的转换，将其转换为树上路径修改这类操作，使用重剖维护起来就相对轻松了。
一个简单的例子：P3398 仓鼠找 sugar
给定一棵 \(n\) 个节点的树，\(q\) 次询问，每次给出一个四元组 \((a, b, c, d)\)，查询 \(a\rightarrow b\) 的路径和 \(c\rightarrow d\) 的路径是否有交。
\(1\leq n, q\leq 10 ^ 5\)。
当然这道题可以用普通的分类讨论通过，但是转化后使用重剖处理则来的更简单一点。我们不妨将原问题看作询问从 \(a\) 点到 \(b\) 点是否经过 \(c \rightarrow d\) 这条路径上的某个点。
考虑将 \(c \rightarrow d\) 这条路径上的所有点权值设为 \(1\)，则上述问题等价于求 \(a \rightarrow b\) 的路径权值和是否大于 \(1\)。后面就简单了，使用重剖 + 树状数组维护一下就好了，我们甚至还可以将它加强为求两条路径的交点个数。
由此可见，对于这种两条路径有重叠部分，需要维护这类重叠性信息的时候，我们不妨考虑将其中一条看作修改操作，另一条看作查询操作，查询前一条路径对该路径的影响，这样就能很好地刻画出重剖所能维护的模型。
一些习题：
P3950 部落冲突 | 可达性的简单转换。
P4211 [LNOI2014] LCA | 考虑如何用重叠性刻画 \(\text{dep}_{\text{LCA}(u, v)}\)。
P5305 [GXOI/GZOI2019] 旧词 | 同上，不过要求的东西多了个 \(k\) 次方，需要对维护的东西稍作修改。
P2542 [AHOI2005] 航线规划 | 动态维护割边，考虑形成一个环会发生什么。
2. 长链剖分
2.1 相关定义
2.2 性质
3. 实链剖分
对于 LCT 这块还没有完全理解和掌握，以后学会了再写。
参考资料
-
文字排版方面，参考了 Alex_Wei 老师的博客文章。
-
插图使用 \(\TeX\) 的 TikZ 宏包绘制，风格参考【笔记】平衡树 学习笔记（上）- 离散小波变换°。