当前位置：首页 > news >正文

树链剖分（树剖）算法详解：从原理到实现

news 2026/7/27 0:21:46

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; }