最近公共祖先（LCA）

#include <bits/stdc++.h>

using namespace std;

int n, m, s;

struct D {
    int d;
    int f[22];
} a[500005];

vector<int> e[500005];

void dfs (int x) {
    a[x].d = a[a[x].f[0]].d + 1;
    for (int i = 0; i < e[x].size(); i++) {
        if (e[x][i] != a[x].f[0]) {
            a[e[x][i]].f[0] = x;
            dfs(e[x][i]);
        }
    }
}

void init () {
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[j].d >= (1 << i)) {
                a[j].f[i] = a[a[j].f[i - 1]].f[i - 1];
            }
        }
    }
}

int lca (int x, int y) {
    if (a[x].d > a[y].d) {
        swap(x, y);
    }
    for (int i = 20; i >= 0; i--) {
        if ((a[y].d - a[x].d) >= (1 << i)) {
            y = a[y].f[i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 20; i >= 0; i--) {
        if (a[x].f[i] != a[y].f[i]) {
            x = a[x].f[i], y = a[y].f[i];
        }
    }
    return a[x].f[0];
}

int main () {
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(s);
    init();
    while (--m) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << '\n';
    }
    return 0;
}