C++中的LCA（最近公共祖先）详解

LCA（Lowest Common Ancestor） 指树结构中两个节点的最近公共祖先节点（深度最大的共同祖先）。常用于解决树上的路径查询、距离计算等问题。

核心算法（倍增法）

1. 预处理（DFS）：
   • 记录每个节点的深度 depth[]；
   • 构建倍增表 parent[u][k]，表示节点 u 向上跳 $2^k$ 步的祖先。
2. 查询步骤：
   • 对齐深度：将深度较大的节点上跳到与另一节点同深度；
   • 同步上跳：从最大步长 $k$ 开始尝试（$k={\log }_2(\text{树深度})$），若祖先不同则同步上跳；
   • 返回结果：最终父节点即为LCA。

C++代码实现

#include <vector>
#include <cmath>
#define MAXN 100000  // 最大节点数
using namespace std;

vector<int> tree[MAXN];    // 邻接表存树
int depth[MAXN];           // 节点深度
int parent[MAXN][20];      // 倍增表：parent[u][k] = u的2^k级祖先

// 预处理DFS（初始化深度及倍增表）
void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    parent[u][0] = p;
    for (int k = 1; k < 20; k++) {  // 20足够覆盖2^20深度的树
        if (parent[u][k-1] != -1) {
            parent[u][k] = parent[parent[u][k-1]][k-1];
        }
    }
    for (int v : tree[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

// LCA查询函数
int lca(int u, int v) {
    // 步骤1: 对齐深度
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; diff; k++) {
        if (diff & 1) u = parent[u][k];
        diff >>= 1;
    }
    
    // 步骤2: 同步上跳
    if (u == v) return u;  // v是u的祖先
    for (int k = 19; k >= 0; k--) {
        if (parent[u][k] != parent[v][k]) {
            u = parent[u][k];
            v = parent[v][k];
        }
    }
    return parent[u][0];  // 返回最终父节点
}

// 初始化调用
int main() {
    memset(parent, -1, sizeof(parent));
    depth[0] = -1;  // 假设根节点为1，其父节点0深度为-1
    dfs(1, 0);       // 从根节点1开始DFS
    // 查询示例: lca(4, 5)
}

关键点说明

1. 时间复杂度：
   • 预处理：$O(N\times {\log }_{2}N)$
   • 单次查询：$O({\log }_{2}N)$
2. 适用场景：
   • 静态树结构（无动态修改）
   • 频繁查询场景（如竞赛题目）
3. 空间优化：
   • 倍增表大小：parent[MAXN][log2(MAXN)]
   • 实际中取 $k_{\max }=20$ 可覆盖 $10^6$ 节点

其他解法对比