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

1. 什么是长链剖分长链剖分Long Chain Decomposition是一种针对有根树的链剖分方法常用于解决树上与深度、距离相关的静态查询问题。与重链剖分Heavy-Light Decomposition不同长链剖分优先选择子树中最深的儿子作为“长儿子”从而将树分解为若干条“长链”。长链剖分的核心思想是对于每个节点选择其子树深度最大的儿子作为“长儿子”然后将该节点与其长儿子连接成同一条链。这样整棵树就被分解为若干条从某个节点开始一直沿着长儿子向下延伸的链这些链被称为“长链”。2. 长链剖分的构建长链剖分的构建可以通过一次深度优先搜索DFS完成时间复杂度为 O(n)。算法步骤第一次 DFS计算每个节点的深度depth和子树最大深度max_depth。第二次 DFS为每个节点确定“长儿子”即子树最大深度最大的儿子。从根节点开始将每个节点与其长儿子连接形成长链。3. 代码实现C#include bits/stdc.h using namespace std; const int N 1e5 5; vectorint 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 典型应用树上 k 级祖先查询预处理 O(n log n)查询 O(1)。树上两点距离查询结合 LCA可以快速计算任意两点距离。子树深度相关统计如子树中深度为 d 的节点数量。优化树上 DP通过指针继承技巧将某些树形 DP 的复杂度从 O(n²) 降为 O(n)。5. 长链剖分 vs 重链剖分对比维度长链剖分重链剖分选择标准子树深度最大的儿子子树大小最大的儿子链长特点链较长数量较少链较短数量较多主要应用深度、距离相关查询路径修改、子树查询复杂度通常 O(n)O(n log n)代码难度相对简单相对复杂6. 实战例题6.1 例题树上 k 级祖先问题描述给定一棵 n 个节点的有根树有 q 次查询每次查询给出节点 u 和整数 k求 u 的第 k 级祖先如果不存在则输出 -1。数据范围n, q ≤ 10⁵。长链剖分解法思路预处理每个节点的 2^i 级祖先倍增。对每条长链预处理从链顶向上/向下走链长步的所有节点。查询时先利用倍增跳到 2^h 级祖先使得剩余步数小于链长然后通过预处理的链信息 O(1) 得到答案。7. 总结长链剖分是一种高效的树上问题处理技巧特别适合解决与深度、距离相关的静态查询问题。通过优先选择深度最大的儿子将树分解为较少的长链从而在预处理和查询时获得优异的时间复杂度。掌握长链剖分需要理解其构建过程、核心性质以及指针继承等优化技巧。建议通过实际编码练习来加深理解特别是树上 k 级祖先、深度统计等经典问题。