题解 | 【模板】最近公共祖先（LCA）

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

int n, m, r;
int fa[N][20], d[N];

vector<int> e[N];

inline void build(int x, int f) {
    fa[x][0] = f;
    d[x] = d[f] + 1;
    for(int i = 1; i < 20; i++) fa[x][i] = fa[fa[x][i-1]][i-1];
    for(int i : e[x]) {
        if(i == f) continue;
        build(i, x);
    }
}

inline int lca(int x, int y) {
    if(d[y] < d[x]) swap(x, y);
    int tmp = d[y] - d[x];
    for(int i = 19; i >= 0; i--) {
        if(tmp >= (1 << i)) {
            tmp -= (1 << i);
            y = fa[y][i];
        }
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--) {
        if(fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>r;
    for(int i = 1; i < n; i++) {
        int x, y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    build(r, 0);
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin>>a>>b;
        cout<<lca(a, b)<<'\n';
    }
    return 0;
}