树链剖分 (Heavy-Light Decomposition / HLD)¶
树链剖分（重链剖分，简称“树剖” / HLD） 是树上高级算法与数据结构的核心枢纽。它通过将一棵树划分为若干条互不相交的线性链（重链），并将整棵树上的节点通过深度优先搜索序（DFS 序）映射为一维数组，从而使得树上任意路径和任意子树均能完美对应为若干段连续的线性区间。
结合线段树（Segment Tree）或树状数组（BIT）后，树链剖分能够以极高的效率解决树上动态问题：
- 树上两点间的最近公共祖先 (LCA)：单次 \(\mathcal{O}(\log N)\)，常数远小于树上倍增；
- 树上两点间路径的权值修改与查询：单次 \(\mathcal{O}(\log^2 N)\)；
- 任意子树的权值修改与查询：单次 \(\mathcal{O}(\log N)\)。
1. 核心概念与基本定义¶
对于一棵包含 \(N\) 个节点的有根树，我们通过子树规模的大小将树的节点和边进行分类：
- 重儿子（Heavy Son）：对于非叶子节点 \(u\)，其所有子节点中子树大小（节点总数 \(size\)）最大的子节点 \(v\) 称为 \(u\) 的重儿子。若有多个子节点的子树大小相同且并列最大，任选其一；叶子节点没有重儿子。
- 轻儿子（Light Son）：节点 \(u\) 的子节点中，除重儿子以外的所有其他子节点均为轻儿子。
- 重边（Heavy Edge）：连接父节点与它的重儿子的连边。
- 轻边（Light Edge）：连接父节点与它的轻儿子的连边。
- 重链（Heavy Path）：由若干条连续的重边首尾相连构成的极大路径。每个叶子节点若不是重儿子，则自己单独构成一条仅包含自身的重链。树上的每一个节点有且仅属于一条重链。
- 链头（Top of Heavy Path）：一条重链中深度最小（最靠近根）的节点，称为该重链的链头，记作 \(top[u]\)。
2. 关键定理与数学复杂度证明¶
树链剖分之所以能在对数复杂度内完成复杂的树上路径操作，完全仰赖以下三个核心数学定理：
2.1 轻边翻倍定理¶
定理 1： 从树上任意节点 \(u\) 沿父节点指针一路向上走到根节点，沿途经过的轻边数量至多为 \(\lfloor \log_2 N \rfloor\) 条。
证明： 设节点 \(v\) 是节点 \(p\) 的轻儿子（即边 \((p, v)\) 是一条轻边）。 根据重儿子的定义，父节点 \(p\) 必定存在一个重儿子 \(h\)，满足：
\[
size(h) \ge size(v)
\]
由于节点 \(p\) 的子树大小包含了自身、重儿子 \(h\) 的子树、轻儿子 \(v\) 的子树以及其余可能的轻儿子子树，因此有：
\[
size(p) > size(h) + size(v) \ge 2 \cdot size(v) \implies size(v) < \frac{1}{2} size(p)
\]
这表明：每当我们逆向跨越一条轻边 \((v, p)\) 向上走一步，当前节点的子树大小至少翻倍（严格大于原来的 2 倍）。 整棵树的最大节点总数为 \(N\)，而单个节点的子树大小至少为 \(1\)。由 \(1 \cdot 2^k \le N\) 可知，从任意节点走到根节点，至多只能发生 \(\log_2 N\) 次翻倍。因此经过的轻边条数不会超过 \(\lfloor \log_2 N \rfloor\)。
2.2 重链跳转定理¶
定理 2： 从树上任意节点 \(u\) 沿父节点指针一路向上走到根节点，至多跨越 \(\mathcal{O}(\log N)\) 条互不相同的重链。
证明： 每离开一条重链的链头向上迈出一步，走过的必定是一条轻边（因为如果上一步还是重边，链头就会继续向上延伸，与链头的极大性矛盾）。 由定理 1，向上走经过的轻边数量不超过 \(\log_2 N\)，因此跨越的重链数量也必然不超过 \(\log_2 N + 1 = \mathcal{O}(\log N)\) 条。
2.3 DFS 序连续性定理（数据结构桥梁）¶
定理 3： 在第二次深度优先搜索（DFS 2）分配时间戳时，若严格优先递归遍历每个节点的重儿子，则： 1. 同一条重链上的所有节点，其分配到的 DFS 序（
dfn）是严格连续的； 2. 任意节点 \(u\) 的整棵子树内的所有节点，其分配到的 DFS 序（dfn）也是严格连续的，对应区间严格为 \([dfn[u], dfn[u] + size[u] - 1]\)。
意义：
- 树上任意一条两点路径 \(u \to v\)，可以拆分为 \(\mathcal{O}(\log N)\) 条重链上的连续线段；
- 树上任意一个节点的子树，本身就是一段单一连续线段；
- 这使得我们能把一棵树上的路径与子树问题，100% 降维转化为一维区间问题，直接交由线段树进行区间加、区间求和或区间最值维护！
3. 算法实现：两次经典的深度优先搜索 (Two-Pass DFS)¶
树链剖分的预处理由两个各司其职的 DFS 构成：
(标注* 为重边，1 - 2 - 4 构成一条重链，其 DFS 序连续排布)
3.1 第一次 DFS（dfs1）：基础树形拓扑信息¶
计算每个节点的以下属性：
depth[u]：节点深度（根节点深度设为 1）；parent[u]：父节点编号；size[u]：子树大小（节点自身及其所有后代总数）；heavy[u]：重儿子编号（子树规模最大的子节点，无子节点时为 0）。
void dfs1(int u, int p, int d) {
depth[u] = d;
parent[u] = p;
size[u] = 1;
heavy[u] = 0;
int max_sub = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u, d + 1);
size[u] += size[v];
if (size[v] > max_sub) {
max_sub = size[v];
heavy[u] = v; // 动态更新重儿子
}
}
}
3.2 第二次 DFS（dfs2）：重链划分与 DFS 序映射¶
计算每个节点的重链归属并分配连续时间戳：
dfn[u]：节点 \(u\) 的 DFS 序（时间戳）；rnk[cnt]：时间戳对应的节点编号（dfn的逆映射，用于线段树建树初始化）；top[u]：节点 \(u\) 所在重链的链头节点。
void dfs2(int u, int h) {
top[u] = h;
dfn[u] = ++timer;
rnk[timer] = u;
// 1. 关键：优先递归重儿子，保证同一重链上的 dfn 严格连续
if (heavy[u]) {
dfs2(heavy[u], h); // 重儿子继承当前重链的链头 h
}
// 2. 依次递归各个轻儿子
for (int v : adj[u]) {
if (v == parent[u] || v == heavy[u]) continue;
dfs2(v, v); // 轻儿子成为一条全新重链的链头，其 top 为自身
}
}
4. 树上操作与线段树结合¶
4.1 极速求解最近公共祖先 (LCA)¶
相比于树上倍增法，重链剖分求 LCA 的思想极为直观：让链头更深的点沿着重链一路向上“蹦迪”，当两点处于同一条重链时，深度较浅的点即为 LCA。
int get_lca(int u, int v) const {
// 当两点不在同一条重链上时
while (top[u] != top[v]) {
// 比较两点所在重链链头的深度，让链头更深者向上跳
if (depth[top[u]] < depth[top[v]]) {
std::swap(u, v);
}
// u 跳到其重链链头的父节点处
u = parent[top[u]];
}
// 此时两点已在同一条重链上，深度较浅者即为 LCA
return depth[u] < depth[v] ? u : v;
}
常数优势： 倍增法需要循环 20 次尝试跳跃；而重链剖分每次跳跃跨越一条完整重链，实际随机树上平均跳跃次数仅为 \(1 \sim 3\) 次，最坏也不超过 \(\log_2 N\) 次，常数仅为倍增法的 \(1/3 \sim 1/5\)。
4.2 树上两点路径的修改与查询 (\(u \leftrightarrow v\))¶
当我们需要对 \(u\) 到 \(v\) 的最短简单路径上的所有节点执行区间加或区间求和时：
- 当 \(top[u] \ne top[v]\) 时，设 \(depth[top[u]] \ge depth[top[v]]\)：
- 节点 \(top[u]\) 到 \(u\) 处于同一条重链上，其 DFS 序区间为 \([dfn[top[u]], dfn[u]]\)；
- 在线段树上操作区间 \([dfn[top[u]], dfn[u]]\)；
- 令 \(u \leftarrow parent[top[u]]\)，继续循环；
- 当 \(top[u] == top[v]\) 时，两点已在同一条重链上：
- 设 \(depth[u] \le depth[v]\)，在线段树上操作最后一段区间 \([dfn[u], dfn[v]]\)。
// 示例：查询树上 u 到 v 路径上的点权和
long long query_path(int u, int v) {
long long ans = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
ans += seg_tree.query(dfn[top[u]], dfn[u]);
u = parent[top[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
ans += seg_tree.query(dfn[u], dfn[v]);
return ans;
}
4.3 子树修改与查询¶
由定理 3，以 \(u\) 为根的整棵子树在 DFS 序中是一段连续区间 \([dfn[u], dfn[u] + size[u] - 1]\)。 因此子树修改或查询完全不需要向上跳链，仅需进行一次线段树单区间操作，时间复杂度严格为 \(\mathcal{O}(\log N)\)：
// 示例：对以 u 为根的整棵子树所有节点加上 val
void update_subtree(int u, long long val) {
seg_tree.add(dfn[u], dfn[u] + size[u] - 1, val);
}
// 示例：查询以 u 为根的子树点权和
long long query_subtree(int u) {
return seg_tree.query(dfn[u], dfn[u] + size[u] - 1);
}
4.4 点权与边权转化技巧¶
许多题目要求维护的是树上的边权，而非点权。可以通过“边权下放（Push Down to Children）”无缝套用树剖：
- 在有根树中，除根节点外，每个节点有且仅有一条连向父节点的入边；
- 因此，我们可以将边 \((u, v)\) 的权值存储在深度更深的那个节点上；
- 路径查询的关键修正：
- 查询 \(u \to v\) 的路径边权时，两点的最近公共祖先 \(LCA(u, v)\) 所存储的边权是它与其父节点的连边，并不属于 \(u \to v\) 路径内部！
- 因此在跳跃至同一条重链后，最后的线段树操作区间应当避开 LCA 自身： 从 \([dfn[u], dfn[v]]\) 变更为 \([dfn[u] + 1, dfn[v]]\)（假设 \(depth[u] < depth[v]\)）。若 \(u == v\)，则直接结束，不产生任何区间贡献。
5. 进阶拓展：长链剖分与 DSU on Tree¶
除了以子树大小 \(size\) 为权重的重链剖分外，树链剖分思想还有两大极其璀璨的衍生模型：
5.1 树上启发式合并 (DSU on Tree)¶
在求解树上每个节点的子树集合信息（如子树内出现频次、不同元素计数等）时，直接利用重链剖分的信息：
- 优先递归解决所有轻儿子的子树，并清空轻儿子占用的全局状态；
- 递归解决重儿子的子树，且保留重儿子占用的全局状态；
- 将所有轻儿子的子树暴力统计并入当前节点；
- 复杂度优势：因为每个轻儿子所在的子树规模不到父节点的一半，任何节点向上走到根只会作为轻儿子被暴力扫描 \(\mathcal{O}(\log N)\) 次。总体时间复杂度稳定在 \(\mathcal{O}(N \log N)\)（典型如 LeetCode 2003）。
5.2 长链剖分 (Long-Chain Decomposition)¶
将选重儿子的策略从“子树大小最大”改为“子树最大深度（高）最大”：
- 链长性质：任意节点向上跳长链，经过的链长累加构成的几何级数使得整棵树的轻链跳转次数同样受控；
- \(\mathcal{O}(1)\) 查询树上 \(k\) 级祖先：利用树上倍增跳 \(2^{\lfloor \log_2 k \rfloor}\) 步，再利用长链定位与定长数组向前/后偏置，实现严格 \(\mathcal{O}(1)\) 在线查询任意 \(k\) 级祖先；
- \(\mathcal{O}(N)\) 优化深度相关 DP：以深度为第一维下标的树形 DP（例如“子树内距离为 \(d\) 的点数”），重儿子直接指针 \(\mathcal{O}(1)\) 继承，轻儿子暴力合并，整体复杂度从 \(\mathcal{O}(N^2)\) 线性降至 \(\mathcal{O}(N)\)。
6. 现代 C++ 工业级解耦模板¶
本模板将树剖拓扑逻辑与底层的线段树实现彻底解耦，不仅代码结构清晰，而且无论是维护加和、最大值、异或还是边权，只需替换区间操作谓词即可复用。
#include <vector>
#include <algorithm>
#include <iostream>
// ==================== 1. 延迟标记线段树 (Lazy Segment Tree) ====================
class SegmentTree {
private:
int n;
std::vector<long long> tree, lazy;
void push_down(int node, int l, int r) {
if (lazy[node] != 0) {
int mid = l + (r - l) / 2;
lazy[2 * node] += lazy[node];
tree[2 * node] += lazy[node] * (mid - l + 1);
lazy[2 * node + 1] += lazy[node];
tree[2 * node + 1] += lazy[node] * (r - mid);
lazy[node] = 0;
}
}
void update_range(int node, int l, int r, int ql, int qr, long long val) {
if (ql <= l && r <= qr) {
tree[node] += val * (r - l + 1);
lazy[node] += val;
return;
}
push_down(node, l, r);
int mid = l + (r - l) / 2;
if (ql <= mid) update_range(2 * node, l, mid, ql, qr, val);
if (qr > mid) update_range(2 * node + 1, mid + 1, r, ql, qr, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
long long query_range(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[node];
push_down(node, l, r);
int mid = l + (r - l) / 2;
long long res = 0;
if (ql <= mid) res += query_range(2 * node, l, mid, ql, qr);
if (qr > mid) res += query_range(2 * node + 1, mid + 1, r, ql, qr);
return res;
}
public:
SegmentTree(int n) : n(n), tree(4 * n + 5, 0), lazy(4 * n + 5, 0) {}
void add(int ql, int qr, long long val) {
if (ql > qr) return;
update_range(1, 1, n, ql, qr, val);
}
long long query(int ql, int qr) {
if (ql > qr) return 0;
return query_range(1, 1, n, ql, qr);
}
};
// ==================== 2. 树链剖分核心拓扑封装 ====================
class HeavyLightDecomposition {
private:
int n, root;
int timer;
std::vector<std::vector<int>> adj;
std::vector<int> parent, depth, size, heavy, top, dfn, rnk;
SegmentTree seg;
void dfs1(int u, int p, int d) {
depth[u] = d;
parent[u] = p;
size[u] = 1;
heavy[u] = 0;
int max_s = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u, d + 1);
size[u] += size[v];
if (size[v] > max_s) {
max_s = size[v];
heavy[u] = v;
}
}
}
void dfs2(int u, int h) {
top[u] = h;
dfn[u] = ++timer;
rnk[timer] = u;
if (heavy[u]) dfs2(heavy[u], h);
for (int v : adj[u]) {
if (v == parent[u] || v == heavy[u]) continue;
dfs2(v, v);
}
}
public:
HeavyLightDecomposition(int n, int root = 1)
: n(n), root(root), timer(0), adj(n + 1), parent(n + 1),
depth(n + 1), size(n + 1), heavy(n + 1), top(n + 1),
dfn(n + 1), rnk(n + 1), seg(n) {}
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void build(const std::vector<long long> &init_val) {
dfs1(root, 0, 1);
dfs2(root, root);
for (int i = 1; i <= n; ++i) {
seg.add(dfn[i], dfn[i], init_val[i]);
}
}
// 快速 LCA
int get_lca(int u, int v) const {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
u = parent[top[u]];
}
return depth[u] < depth[v] ? u : v;
}
// 路径区间修改 (u -> v 点权增加 val)
void update_path(int u, int v, long long val) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
seg.add(dfn[top[u]], dfn[u], val);
u = parent[top[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
seg.add(dfn[u], dfn[v], val);
}
// 路径区间查询 (u -> v 点权和)
long long query_path(int u, int v) {
long long res = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
res += seg.query(dfn[top[u]], dfn[u]);
u = parent[top[u]];
}
if (depth[u] > depth[v]) std::swap(u, v);
res += seg.query(dfn[u], dfn[v]);
return res;
}
// 子树修改 (以 u 为根的子树点权增加 val)
void update_subtree(int u, long long val) {
seg.add(dfn[u], dfn[u] + size[u] - 1, val);
}
// 子树查询 (以 u 为根的子树点权和)
long long query_subtree(int u) {
return seg.query(dfn[u], dfn[u] + size[u] - 1);
}
};
7. 经典实战好题与模型精析¶
-
洛谷 P3384 - 【模板】重链剖分 / 树链剖分
普及+/提高提示
树链剖分的经典标准教科书题。
- 维护树上的 4 种操作：路径加、路径求和、子树加、子树求和（对质数 \(P\) 取模）。
- 按照上述模板完整实现：第一次 DFS 算子树大小与重儿子，第二次 DFS 算时间戳与重链头，将树上操作完整映射到线段树上完成。
-
LeetCode 2003 - 每棵子树内缺失的最小基因值 (Smallest Missing Genetic Value in Each Subtree)
困难提示
树链剖分思想之重儿子保留 (DSU on Tree)。
- 求解每个子树未出现的最小正整数（MEX）。
- 运用重链剖分重儿子优先的性质：先递归轻儿子（算完后擦除集合标记），再递归重儿子（保留重儿子集合数据），最后合并轻儿子节点，更新子树 MEX。
- 注：本题由于基因值互异，亦可使用自底向上爬链的 \(\mathcal{O}(N)\) 最优特化解法（详见 MEX 专题）。
-
LeetCode 2458 - 移除子树后的二叉树高度 (Height of Binary Tree After Subtree Removal Queries)
困难提示
DFS 序连续性定理的应用。
- 每次询问：若把以节点 \(query\) 为根的子树完全删除，整棵树剩余节点的最大深度是多少？
- 利用树剖的核心性质：节点 \(u\) 的子树对应的 DFS 序恰好是连续闭区间 \([dfn[u], dfn[u] + size[u] - 1]\)。
- 删除该子树，等价于在 DFS 序数组中挖掉这一段连续区间，剩余部分变成了左前缀 \([1, dfn[u]-1]\) 和右后缀 \([dfn[u]+size[u], N]\)。
- 预处理 DFS 序深度的前后缀最大值数组，单次查询只需 \(\mathcal{O}(1)\) 即可得到删除后的树高。
-
LeetCode 2509 - 查询树中环的长度 (Cycle Length Queries in a Tree)
中等提示
满二叉树链跳跃求 LCA。
- 满二叉树中节点 \(x\) 的父节点恰为 \(\lfloor x / 2 \rfloor\)。添加一条边 \((a, b)\) 形成环的长度等于 \(dist(a, b) + 1\)。
- 利用类似树剖跳重链的贪心对齐思想：只要 \(a \ne b\)，每次让数值更大（即深度更深）的节点跳至其父节点（\(a \leftarrow a / 2\) 或 \(b \leftarrow b / 2\)），步数累加 1。当 \(a == b\) 时即到达 LCA，总环长为累加步数 \(+ 1\)。单次查询 \(\mathcal{O}(\log N)\)。
-
Codeforces 916E - Jamie and Tree
2400提示
动态换根树链剖分标杆题。
- 树链剖分通常需要固定根节点建树，若支持操作
make_root(r)，如何避免重新打标重建树剖？ - 核心技巧在于换根时的分类讨论（依然使用固定根 \(1\) 建树剖）：
- 查询两点在当前根 \(r\) 下的 LCA：分别计算 \(L_1 = LCA(u, v), L_2 = LCA(u, r), L_3 = LCA(v, r)\)，取其中深度最大的那个即为换根后的真正 LCA；
- 对子树 \(u\) 操作：
- 若 \(u == r\)：整棵树都被修改，操作区间为 \([1, N]\)；
- 若 \(r\) 在 \(u\) 的子树外（即 \(LCA(u, r) \ne u\)）：\(u\) 的子树结构与固定根时完全相同，直接操作区间 \([dfn[u], dfn[u] + size[u] - 1]\)；
- 若 \(r\) 在 \(u\) 的子树内（即 \(LCA(u, r) == u\)）：换根后，\(u\) 的子树包含了除“包含 \(r\) 的那个 \(u\) 的直接子节点的整棵子树”之外的其余所有节点！通过倍增找到该直接子节点 \(s\)，操作全区间扣除 \([dfn[s], dfn[s] + size[s] - 1]\) 即可。
- 树链剖分通常需要固定根节点建树，若支持操作
-
SPOJ QTREE - Query on a tree
经典提示
树剖维护边权最大值的始祖题。
- 树上单点修改某条边的权值，区间查询两点路径上的最大边权。
- 采用边权下放到较深节点的转化技巧。线段树维护区间最大值，单点修改直接更新目标点的 \(dfn\) 对应位置；路径查询在跳到同一条重链后，区间查询 \([dfn[u]+1, dfn[v]]\) 排除 LCA 节点本身。