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. 树链剖分的预处理两次 DFS3.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. 时间复杂度分析预处理两次 DFSO(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; vectorint 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() { // 读入树 // 第一次 DFSdfs1(root, 0) // 第二次 DFSdfs2(root, root) // 将原权值 w[u] 按 DFS 序存入 nw[dfn[u]] // 建线段树 seg.build(1, 1, n, nw) // 处理询问 return 0; }8. 总结与扩展树链剖分的优势将树上路径问题转化为序列区间问题可以套用丰富的序列数据结构。预处理 O(n)单次路径操作 O(log²n)在大多数题目中足够高效。思想清晰模板性强学会后可以解决一大类树上路径问题。常见变体与应用边权转点权将边权赋给深度较大的端点查询时注意 LCA 处权值不计入。结合树状数组如果只有单点修改、区间查询可以用树状数组代替线段树。维护路径最值将线段树的求和改为求最大值/最小值。结合可持久化线段树实现树上路径第 k 大等查询。树链剖分是算法竞赛中处理树上路径问题的利器理解其“重链剖分区间维护”的核心思想后便能灵活应用于各种变式题目。
树链剖分（树剖）算法详解：从原理到实现
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. 树链剖分的预处理两次 DFS3.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. 时间复杂度分析预处理两次 DFSO(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; vectorint 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() { // 读入树 // 第一次 DFSdfs1(root, 0) // 第二次 DFSdfs2(root, root) // 将原权值 w[u] 按 DFS 序存入 nw[dfn[u]] // 建线段树 seg.build(1, 1, n, nw) // 处理询问 return 0; }8. 总结与扩展树链剖分的优势将树上路径问题转化为序列区间问题可以套用丰富的序列数据结构。预处理 O(n)单次路径操作 O(log²n)在大多数题目中足够高效。思想清晰模板性强学会后可以解决一大类树上路径问题。常见变体与应用边权转点权将边权赋给深度较大的端点查询时注意 LCA 处权值不计入。结合树状数组如果只有单点修改、区间查询可以用树状数组代替线段树。维护路径最值将线段树的求和改为求最大值/最小值。结合可持久化线段树实现树上路径第 k 大等查询。树链剖分是算法竞赛中处理树上路径问题的利器理解其“重链剖分区间维护”的核心思想后便能灵活应用于各种变式题目。
