1. 什么是 LCA？
LCA（Lowest 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; vector<vector<int>> adj, up; vector<int> 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, vector<vector<int>>& tree, int root = 0) { this->n = n; LOG = ceil(log2(n)); adj = tree; up.assign(n, vector<int>(LOG+1)); 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 { List<Integer>[] tree; List<Pair>[] 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 Tour | O(n) | O(1) | O(n log n) | 需要 O(1) 查询，可接受较大空间 |
7. 总结
LCA 是树算法中的基础且重要的组件，掌握其原理和不同实现方法对于解决树相关问题至关重要。在实际应用中：
- 对于一般竞赛和面试，掌握倍增算法足够应对大多数情况。
- 如果需要处理大量查询且查询已知，Tarjan 离线算法是最优选择。
- 在需要 O(1) 查询且内存充足时，可以考虑 RMQ + Euler Tour 方法。
理解 LCA 不仅有助于解决具体问题，还能加深对树结构、DFS 序、二进制思想等基础算法概念的理解。
