最近公共祖先（LCA）CSP-S

💡 核心思想

最近公共祖先（LCA）是树结构中两个节点的最深公共祖先。倍增法是最高效的在线算法：预处理每个节点的 2^k 级祖先，查询时先将较深的节点上跳到同一深度，然后同时上跳直到找到 LCA。预处理 O(n log n)，每次查询 O(log n)。

🎯 直觉理解

想象一棵家族树，要找两个人的最近共同祖先。先把辈分低的那个往上抬，直到两人同辈；然后两人一起往上抬，第一次相遇的地方就是最近公共祖先。倍增法就像"坐电梯"：不是一级一级往上走，而是先坐 16 层电梯，再坐 8 层，再坐 4 层……快速对齐。

📝 算法流程

1. DFS/BFS 求出每个节点的深度 depth[u]
2. 预处理 fa[u][k]：u 的 2^k 级祖先（fa[u][0] 是直接父节点）
3. 查询时：如果 depth[u] < depth[v]，交换 u 和 v
4. 将 u 向上跳 depth[u] - depth[v] 层，使 u 和 v 同深
5. 从大到小枚举 k：如果 fa[u][k] != fa[v][k]，则 u = fa[u][k], v = fa[v][k]
6. 最后返回 fa[u][0]（即父节点）

$$fa[u][k] = fa[fa[u][k-1]][k-1] \text{（u 的 2^k 祖先是其 2^{k-1} 祖先的 2^{k-1} 祖先）}$$

$$\text{查询：将较深的节点上跳 }Delta = |depth[u] - depth[v]|\text{ 层，然后同步上跳}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

const int MAXN = 100005;
const int LOG = 20;

vector g[MAXN];
int depth[MAXN], fa[MAXN][LOG];

void dfs(int u, int f) {
    depth[u] = depth[f] + 1;
    fa[u][0] = f;
    for (int k = 1; k < LOG; k++)
        fa[u][k] = fa[fa[u][k-1]][k-1];
    for (int v : g[u])
        if (v != f) dfs(v, u);
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 1. 将 u 上跳到与 v 同深
    int diff = depth[u] - depth[v];
    for (int k = LOG - 1; k >= 0; k--)
        if (diff >> k & 1) u = fa[u][k];
    if (u == v) return u;
    // 2. 同步上跳
    for (int k = LOG - 1; k >= 0; k--)
        if (fa[u][k] != fa[v][k]) {
            u = fa[u][k];
            v = fa[v][k];
        }
    return fa[u][0];
}

int main() {
    int n = 6;
    // 建树：1-2, 1-3, 2-4, 2-5, 3-6
    g[1].push_back(2); g[2].push_back(1);
    g[1].push_back(3); g[3].push_back(1);
    g[2].push_back(4); g[4].push_back(2);
    g[2].push_back(5); g[5].push_back(2);
    g[3].push_back(6); g[6].push_back(3);
    
    dfs(1, 0);
    cout << lca(4, 5) << endl; // 2
    cout << lca(4, 6) << endl; // 1
    cout << lca(5, 6) << endl; // 1
    return 0;
}

⚠️ 常见坑点

📚 相关题目