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

【板子】LCA 树链剖分

news 2026/7/28 10:24:04

这是另一种非常经典的求解最近公共祖先（LCA）的方法：树链剖分（Heavy-Light Decomposition）。

与Tarjan 算法（离线算法）不同，树链剖分是一种在线算法。

1. 核心概念：什么是“重”和“轻”？

树链剖分的核心思想是将一棵树切分成若干条链，使得在查找路径时效率最高。为了实现这一点，它定义了以下概念：

重儿子 (Heavy Son)：对于节点 u，它的所有子节点中，子树节点数量最多的那个儿子。
轻儿子 (Light Son)：除了重儿子以外的所有儿子。
重边 (Heavy Edge)：连接节点 u 和它的重儿子的边。
轻边 (Light Edge)：连接节点 u 和它的轻儿子的边。
重链 (Heavy Chain)：由多条重边连接而成的路径。

性质：任意一条树上的路径，最多只会被切成 logn 条链。这就是为什么它速度快的原因。

2. 需要维护的数组

为了实现树链剖分，我们需要维护以下几个关键数组：

fa[u]：节点 u 的父节点。
dep[u]：节点 u 的深度（根节点深度通常为 1）。
sz[u]：以 u 为根的子树的节点总数。
son[u]：节点 u 的重儿子（如果没有则为 0）。
top[u]：节点 u 所在重链的顶端节点。

3. 算法流程与代码模板

树链剖分求 LCA 的过程分为两个阶段：两次 DFS 预处理 和在线查询。

第一阶段：预处理（两遍 DFS）

第一遍 DFS (dfs1) 负责计算子树大小、父节点、深度和重儿子。

第二遍 DFS (dfs2) 负责给节点分配链顶（top），将树真正剖分成链。

#include <iostream> #include <vector> #include <cstring> using namespace std; const int N = 500010; vector<int> e[N]; // 邻接表存图 // 树链剖分核心数组 int fa[N], dep[N], son[N], sz[N]; int top[N]; // 链顶数组 // 第一遍 DFS：找重儿子、算大小、算深度 void dfs1(int u, int father) { fa[u] = father; dep[u] = dep[father] + 1; sz[u] = 1; son[u] = 0; // 初始化没有重儿子 for (auto v : e[u]) { if (v == father) continue; dfs1(v, u); sz[u] += sz[v]; // 累加子树大小 // 更新重儿子：如果当前儿子v的子树比之前记录的重儿子还大，就更新 if (sz[v] > sz[son[u]]) { son[u] = v; } } } // 第二遍 DFS：连重链、标记链顶 void dfs2(int u, int t) { top[u] = t; // 记录当前点所在的链顶 if (son[u] == 0) return; // 如果没有重儿子，说明到底了 // 1. 优先递归处理重儿子，重儿子的链顶和当前点一样 dfs2(son[u], t); // 2. 处理轻儿子，轻儿子开启一条新的链 for (auto v : e[u]) { if (v == fa[u] || v == son[u]) continue; dfs2(v, v); // 新的链，链顶就是自己 } } // 核心查询函数：求 u 和 v 的 LCA int lca(int u, int v) { // 核心思想：当两个点不在同一条重链上时，让深度较大的那个点跳到链顶的父亲 while (top[u] != top[v]) { // 优化：总是让深的点往上跳，减少代码行数 if (dep[top[u]] < dep[top[v]]) swap(u, v); // 把 u 跳到链顶的父节点 u = fa[top[u]]; } // 跳出循环时，说明 u 和 v 在同一条重链上了 // 此时深度较小的那个点就是 LCA return dep[u] < dep[v] ? u : v; } int main() { int n; // 节点数 cin >> n; // 读入 n-1 条边建图 for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; e[a].push_back(b); e[b].push_back(a); } // 初始化根节点信息并开始剖分 dfs1(1, 0); // 假设根为 1 dfs2(1, 1); // 处理查询 int q; // 查询次数 cin >> q; while (q--) { int u, v; cin >> u >> v; cout << lca(u, v) << endl; } return 0; }

4. 原理解释（如何求出 LCA？）

lca函数的逻辑利用了“重链”的性质，可以把它想象成在树上“走楼梯”：

不在同一条链上（top[u] != top[v]）：
- 如果 u 和 v 不在同一条重链上，说明它们之间有垂直的距离。
- 我们总是让当前位置比较“深”（dep大）的那个点，沿着它所在的重链一直往上爬，直到到达链顶（top）。
- 然后，再从链顶跳到链顶的父节点（u = fa[top[u]]）。这就相当于跨过了这条重链，进入了另一条链。
- 为什么要从轻儿子开始开新链？ 因为轻儿子的子树大小至少减半，所以每经过一条轻边，子树规模至少减少一半。这保证了从任意节点到根节点的路径上，最多只有 logn 条轻边，从而保证了跳跃次数是 logn 级别的。
在同一条链上（top[u] == top[v]）：
- 当循环结束，说明 u 和 v 终于落在了同一条重链上。
- 因为它们在同一条直线上，所以位置靠下的那个点（深度小的）必然是另一个点的祖先。
- 直接返回dep[u] < dep[v] ? u : v即可。