长链剖分（Long Chain Decomposition）算法详解

1. 什么是长链剖分

长链剖分（Long Chain Decomposition）是一种针对有根树的链剖分方法，常用于解决树上与深度、距离相关的静态查询问题。与重链剖分（Heavy-Light Decomposition）不同，长链剖分优先选择子树中最深的儿子作为“长儿子”，从而将树分解为若干条“长链”。

长链剖分的核心思想是：对于每个节点，选择其子树深度最大的儿子作为“长儿子”，然后将该节点与其长儿子连接成同一条链。这样，整棵树就被分解为若干条从某个节点开始，一直沿着长儿子向下延伸的链，这些链被称为“长链”。

2. 长链剖分的构建

长链剖分的构建可以通过一次深度优先搜索（DFS）完成，时间复杂度为 O(n)。

算法步骤：

1. 第一次 DFS：计算每个节点的深度（depth）和子树最大深度（max_depth）。
2. 第二次 DFS：为每个节点确定“长儿子”（即子树最大深度最大的儿子）。
3. 从根节点开始，将每个节点与其长儿子连接，形成长链。

3. 代码实现（C++）

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<int> g[N]; // 邻接表存树 int depth[N], max_depth[N]; // 深度、子树最大深度 int son[N]; // 长儿子 int top[N]; // 所在长链的顶端节点 // 第一次 DFS：计算深度和子树最大深度 void dfs1(int u, int fa) { depth[u] = depth[fa] + 1; max_depth[u] = depth[u]; for (int v : g[u]) { if (v == fa) continue; dfs1(v, u); max_depth[u] = max(max_depth[u], max_depth[v]); if (max_depth[v] > max_depth[son[u]]) { son[u] = v; // 更新长儿子 } } } // 第二次 DFS：构建长链 void dfs2(int u, int fa, int tp) { top[u] = tp; if (son[u]) { dfs2(son[u], u, tp); // 长儿子继承当前链 } for (int v : g[u]) { if (v == fa || v == son[u]) continue; dfs2(v, u, v); // 其他儿子作为新链的顶端 } } int main() { int n; // 节点数 cin >> n; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); dfs2(1, 0, 1); // 输出每个节点所在长链的顶端 for (int i = 1; i <= n; i++) { cout << "节点 " << i << " 所在长链顶端: " << top[i] << endl; } return 0; }

4. 长链剖分的性质与应用

4.1 主要性质

• 链长性质：每条长链的长度等于链顶端节点的子树最大深度减去该节点的深度。
• 链数上界：长链的数量不超过 O(√n)，实际应用中通常远小于这个上界。
• 深度性质：任意节点到其所在长链顶端的距离不超过该节点子树的最大深度。

4.2 典型应用

1. 树上 k 级祖先查询：预处理 O(n log n)，查询 O(1)。
2. 树上两点距离查询：结合 LCA，可以快速计算任意两点距离。
3. 子树深度相关统计：如子树中深度为 d 的节点数量。
4. 优化树上 DP：通过指针继承技巧，将某些树形 DP 的复杂度从 O(n²) 降为 O(n)。

5. 长链剖分 vs 重链剖分

6. 实战例题

6.1 例题：树上 k 级祖先

问题描述：给定一棵 n 个节点的有根树，有 q 次查询，每次查询给出节点 u 和整数 k，求 u 的第 k 级祖先（如果不存在则输出 -1）。

数据范围：n, q ≤ 10⁵。

长链剖分解法思路：

1. 预处理每个节点的 2^i 级祖先（倍增）。
2. 对每条长链，预处理从链顶向上/向下走链长步的所有节点。
3. 查询时，先利用倍增跳到 2^h 级祖先，使得剩余步数小于链长，然后通过预处理的链信息 O(1) 得到答案。

7. 总结

长链剖分是一种高效的树上问题处理技巧，特别适合解决与深度、距离相关的静态查询问题。通过优先选择深度最大的儿子，将树分解为较少的长链，从而在预处理和查询时获得优异的时间复杂度。

掌握长链剖分需要理解其构建过程、核心性质以及指针继承等优化技巧。建议通过实际编码练习来加深理解，特别是树上 k 级祖先、深度统计等经典问题。