LCA 最近公共祖先

1.倍增法

算法步骤：

1. 先把 x 和 y 提到相同的深度
2. 让 x 和 y 同步向上走，走到 LCA(x, y) 的下一层，x 的父节点即为所求

模板：

#include<bits/stdc++.h>
using namespace std;
const int N = 500005;

int n, m, root;
int depth[N], fa[N][20]; // fa[i][j] : 第 i 个点走 2^j 步走到的父节点

int h[N], e[N << 1], ne[N << 1], idx;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int x, int father){ // 求 x 的深度和 fa[x][]，father是 x 的父节点
    depth[x] = depth[father] + 1; // x 的深度比父节点多 1
    fa[x][0] = father; // 记录父节点
    for(int i = 1; (1 << i) <= depth[x]; i ++){ // 构建 fa[][]数组，它最多到根节点
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for(int i = h[x]; i != -1; i = ne[i]){ // 遍历节点 i 的所有孩子
        int j = e[i];
        if(j != father) dfs(j, x);
    }
}

int lca(int x, int y){
    if(depth[x] < depth[y]) swap(x, y); // 令 x 位于更底层，即 x 的深度值更大
    for(int i = 19; i >= 0; i --){ // 令 x 跳到与 y 同层
        if((depth[x] - depth[y]) & (1 << i)) x = fa[x][i];
    }
    if(x == y) return x; // x 与 y 在同一条边上，y 就是 x 的祖先
    for(int i = 19; i >= 0; i --){ // x 和 y 共同向上跳
        if(fa[x][i] != fa[y][i]){ // 如果祖先相等，说明跳过头了
            x = fa[x][i], y = fa[y][i];
        }
    }
    return fa[x][0]; // 最后 x 位于LCA 的下一层，父节点 fa[x][0] 就是 LCA
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> root;
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; i ++){
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(root, 0);
    while(m --){
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}