LCA（最近公共祖先）算法详解

1. 什么是 LCALCALowest Common Ancestor即最近公共祖先是树结构中的一个经典概念。给定一棵有根树和树中的两个节点它们的最近公共祖先是指距离这两个节点最近的公共祖先节点且该节点同时是这两个节点的祖先。2. LCA 的应用场景树上的路径查询计算两个节点之间的最短路径长度。网络路由在树形网络拓扑中寻找两个节点的最近交汇点。版本控制系统Git 中寻找两个分支的最近共同提交。生物学在系统发育树中寻找两个物种的最近共同祖先。社交网络寻找两个人最近的共同上级或关联节点。3. 基础算法实现3.1 朴素算法暴力向上最直观的方法是分别记录两个节点到根节点的路径然后找到最后一个相同的节点。def lca_naive(parent, u, v): # parent 存储每个节点的父节点根节点的父节点为 -1 path_u [] while u ! -1: path_u.append(u) u parent[u] path_v [] while v ! -1: path_v.append(v) v parent[v] # 从根节点开始比较 i, j len(path_u)-1, len(path_v)-1 lca_node -1 while i 0 and j 0 and path_u[i] path_v[j]: lca_node path_u[i] i - 1 j - 1 return lca_node时间复杂度O(h)其中 h 是树的高度。在最坏情况下链状树为 O(n)。3.2 倍增算法Binary Lifting预处理每个节点向上 2^k 步的祖先查询时通过二进制跳跃快速找到 LCA。class LCA { private: int n, LOG; vectorvectorint adj, up; vectorint depth; void dfs(int u, int p) { up[u][0] p; for(int i 1; i LOG; i) { up[u][i] up[up[u][i-1]][i-1]; } for(int v : adj[u]) { if(v ! p) { depth[v] depth[u] 1; dfs(v, u); } } } public: LCA(int n, vectorvectorint tree, int root 0) { this-n n; LOG ceil(log2(n)); adj tree; up.assign(n, vectorint(LOG1)); depth.assign(n, 0); dfs(root, root); } int query(int u, int v) { if(depth[u] depth[v]) swap(u, v); // 将 u 提到与 v 同一深度 int diff depth[u] - depth[v]; for(int i 0; i LOG; i) { if(diff (1 i)) { u up[u][i]; } } if(u v) return u; // 同时向上跳跃 for(int i LOG; i 0; i--) { if(up[u][i] ! up[v][i]) { u up[u][i]; v up[v][i]; } } return up[u][0]; } };时间复杂度预处理 O(n log n)查询 O(log n)。4. 进阶算法Tarjan 离线算法Tarjan 算法可以在 O(n q) 的时间内处理所有查询但需要提前知道所有查询对。class TarjanLCA { ListInteger[] tree; ListPair[] queries; int[] parent, ancestor; boolean[] visited; int[] result; class Pair { int node, queryId; Pair(int node, int queryId) { this.node node; this.queryId queryId; } } void dfs(int u) { visited[u] true; ancestor[u] u; for(int v : tree[u]) { if(!visited[v]) { dfs(v); union(u, v); ancestor[find(u)] u; } } for(Pair q : queries[u]) { if(visited[q.node]) { result[q.queryId] ancestor[find(q.node)]; } } } // 并查集实现省略... }5. 实战应用示例5.1 计算树上两点距离def tree_distance(lca, depth, u, v): ancestor lca.query(u, v) return depth[u] depth[v] - 2 * depth[ancestor]5.2 判断节点是否在路径上def on_path(lca, depth, u, v, x): # 判断节点 x 是否在 u 到 v 的路径上 lca_uv lca.query(u, v) lca_ux lca.query(u, x) lca_vx lca.query(v, x) # x 在路径上当且仅当 # 1. lca(u, x) x 且 depth[x] depth[lca_uv] # 2. 或 lca(v, x) x 且 depth[x] depth[lca_uv] # 3. 或 lca(u, x) lca_uv 且 lca(v, x) x condition1 (lca_ux x and depth[x] depth[lca_uv]) condition2 (lca_vx x and depth[x] depth[lca_uv]) condition3 (lca_ux lca_uv and lca_vx x) return condition1 or condition2 or condition36. 算法比较与选择算法预处理时间查询时间空间适用场景朴素算法O(1)O(h)O(n)树高度小查询少倍增算法O(n log n)O(log n)O(n log n)通用在线查询Tarjan 离线O(n q)O(1) 均摊O(n q)查询已知需要高效处理大量查询RMQ Euler TourO(n)O(1)O(n log n)需要 O(1) 查询可接受较大空间7. 总结LCA 是树算法中的基础且重要的组件掌握其原理和不同实现方法对于解决树相关问题至关重要。在实际应用中对于一般竞赛和面试掌握倍增算法足够应对大多数情况。如果需要处理大量查询且查询已知Tarjan 离线算法是最优选择。在需要 O(1) 查询且内存充足时可以考虑 RMQ Euler Tour 方法。理解 LCA 不仅有助于解决具体问题还能加深对树结构、DFS 序、二进制思想等基础算法概念的理解。