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 个节点的树，每个节点有一个权值。需要支持两种操作：

1. 将节点 u 到节点 v 的路径上所有节点权值加上 val。
2. 查询节点 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 大等查询。

树链剖分是算法竞赛中处理树上路径问题的利器，理解其“重链剖分+区间维护”的核心思想后，便能灵活应用于各种变式题目。