1. 什么是树链剖分？
树链剖分（Tree Chain Partition，简称树剖）是一种将树形结构转化为线性序列的算法技巧。它通过将树上的路径分解为若干条“重链”，使得原本在树上难以高效处理的路径查询、路径修改等问题，能够借助线段树、树状数组等数据结构在 O(log²n) 或 O(log n) 的时间复杂度内解决。
树剖的核心思想是：通过两次 DFS 预处理，将树上的节点重新编号，使得每条重链上的节点编号连续。这样，树上的任意一条路径都可以被拆分成 O(log n) 段连续的区间，从而可以用维护序列的数据结构来处理。
2. 树链剖分的核心概念
2.1 基本定义
- 重儿子（Heavy Son）：对于节点 u 的所有儿子中，子树大小最大的那个儿子（如果有多个，任选一个）。
- 轻儿子（Light Son）：除重儿子外的其他儿子。
- 重边（Heavy Edge）：连接节点与其重儿子的边。
- 轻边（Light Edge）：连接节点与其轻儿子的边。
- 重链（Heavy Chain）：由重边连续连接形成的极大路径。
2.2 重要数组（预处理结果）
- fa[u]：节点 u 的父节点。
- dep[u]：节点 u 的深度（根节点深度为 0 或 1）。
- size[u]：以 u 为根的子树大小。
- son[u]：节点 u 的重儿子（如果没有，则为 0）。
- top[u]：节点 u 所在重链的顶端节点。
- dfn[u]：节点 u 在 DFS 序中的新编号（时间戳）。
- rnk[dfn[u]]：DFS 序编号对应的原节点，即 rnk[dfn[u]] = u。
3. 树链剖分的预处理（两次 DFS）
3.1 第一次 DFS：计算父节点、深度、子树大小、重儿子
void dfs1(int u, int father) { fa[u] = father; dep[u] = dep[father] + 1; size[u] = 1; son[u] = 0; for (int v : g[u]) { if (v == father) continue; dfs1(v, u); size[u] += size[v]; if (size[v] > size[son[u]]) { son[u] = v; } } }3.2 第二次 DFS：进行重链剖分，分配 DFS 序
int tim = 0; void dfs2(int u, int tp) { top[u] = tp; dfn[u] = ++tim; rnk[tim] = u; // 优先遍历重儿子，保证重链上节点 DFS 序连续 if (son[u]) { dfs2(son[u], tp); } // 遍历轻儿子，轻儿子自己作为新重链的顶端 for (int v : g[u]) { if (v == fa[u] || v == son[u]) continue; dfs2(v, v); } }4. 路径查询与修改
树剖最经典的应用：查询（或修改）树上两点 u, v 之间路径上的节点权值和（或最大值等）。
核心操作：不断将深度较大的点向上跳，每次跳一整条重链，并将这条重链对应的区间（dfn[top[u]] 到 dfn[u]）进行查询/修改。
// 假设有线段树 seg 可以处理区间 [l, r] 的查询/修改 int query_path(int u, int v) { int res = 0; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); // 处理 u 所在的重链区间 [dfn[top[u]], dfn[u]] res += seg.query(1, 1, n, dfn[top[u]], dfn[u]); u = fa[top[u]]; // 跳到上一条重链 } // 此时 u, v 在同一条重链上 if (dep[u] > dep[v]) swap(u, v); res += seg.query(1, 1, n, dfn[u], dfn[v]); return res; }5. 子树查询与修改
由于 DFS 序的性质，以 u 为根的子树中所有节点的新编号 dfn 是连续的：区间 [dfn[u], dfn[u] + size[u] - 1]。因此子树操作可以直接转化为区间操作：
// 查询子树 u 的权值和 int query_subtree(int u) { return seg.query(1, 1, n, dfn[u], dfn[u] + size[u] - 1); } // 修改子树 u 中所有节点的权值（加上 val） void update_subtree(int u, int val) { seg.update(1, 1, n, dfn[u], dfn[u] + size[u] - 1, val); }6. 时间复杂度分析
- 预处理：两次 DFS，O(n)。
- 路径操作：每次跳转将当前节点 u 跳到 fa[top[u]]，由于从叶子到根最多经过 O(log n) 条轻边（每经过一条轻边，子树大小至少翻倍），因此路径会被拆分成 O(log n) 条重链区间。若区间操作（线段树）为 O(log n)，则总复杂度为 O(log²n)。
- 子树操作：O(log n)（线段树区间操作）。
7. 典型例题与代码模板
例题：给定一棵 n 个节点的树，每个节点有一个权值。需要支持两种操作：
- 将节点 u 到节点 v 的路径上所有节点权值加上 val。
- 查询节点 u 到节点 v 的路径上所有节点权值之和。
（完整代码模板较长，此处给出核心结构）
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<int> g[N]; int fa[N], dep[N], size[N], son[N]; int top[N], dfn[N], rnk[N], tim; int w[N]; // 原权值 int nw[N]; // 按 DFS 序排列的权值 // 线段树部分（略） struct SegTree { ... } seg; void dfs1(int u, int f) { ... } void dfs2(int u, int tp) { ... } void update_path(int u, int v, int val) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); seg.update(1, 1, n, dfn[top[u]], dfn[u], val); u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u, v); seg.update(1, 1, n, dfn[u], dfn[v], val); } int query_path(int u, int v) { int res = 0; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); res += seg.query(1, 1, n, dfn[top[u]], dfn[u]); u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u, v); res += seg.query(1, 1, n, dfn[u], dfn[v]); return res; } int main() { // 读入树 // 第一次 DFS：dfs1(root, 0) // 第二次 DFS：dfs2(root, root) // 将原权值 w[u] 按 DFS 序存入 nw[dfn[u]] // 建线段树 seg.build(1, 1, n, nw) // 处理询问 return 0; }8. 总结与扩展
树链剖分的优势：
- 将树上路径问题转化为序列区间问题，可以套用丰富的序列数据结构。
- 预处理 O(n)，单次路径操作 O(log²n)，在大多数题目中足够高效。
- 思想清晰，模板性强，学会后可以解决一大类树上路径问题。
常见变体与应用：
- 边权转点权：将边权赋给深度较大的端点，查询时注意 LCA 处权值不计入。
- 结合树状数组：如果只有单点修改、区间查询，可以用树状数组代替线段树。
- 维护路径最值：将线段树的求和改为求最大值/最小值。
- 结合可持久化线段树：实现树上路径第 k 大等查询。
树链剖分是算法竞赛中处理树上路径问题的利器，理解其“重链剖分+区间维护”的核心思想后，便能灵活应用于各种变式题目。