【板子】LCA 树链剖分

这是另一种非常经典的求解最近公共祖先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; vectorint 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. 原理解释如何求出 LCAlca函数的逻辑利用了“重链”的性质可以把它想象成在树上“走楼梯”不在同一条链上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即可。如图假设查询11911会沿着自己重链上升到4时9显然更深9已经是连顶跳到父节点4此时处于同一个链4为答案。