我基本上都是在文化课上看书学算法，可能用的变量、函数名和大多数人的不一样。

• fa[k]表示k的父亲
• depth[k]表示k的深度（根结点深度为1）
• grand[k][len]表示k的第$2^{len}$个祖宗，也就是说，depth[k]$-$depth[grand[k][len]] = $2^{len}$。当k没有第$2^{len}$个祖宗时，grand[k][len]$=0$。

核心代码都在主函数。

#include <bits/stdc++.h>
using namespace std;

#define MAXN 500000

int n, m, root;
int fa[MAXN + 1], depth[MAXN + 1], granda[MAXN + 1][(int)log2(MAXN) + 1];
list<int> edge[MAXN + 1];

void fa_er(int k, int fa_) {
    fa[k] = fa_;
    for(auto it = edge[k].begin(); it != edge[k].end(); it++) {
        if(*it != fa_) {
            fa_er(*it, k);
        }
    }
}

void depth_er(int k, int fa, int fa_depth) {
    depth[k] = fa_depth + 1;
    for(auto it = edge[k].begin(); it != edge[k].end(); it++) {
        if(*it != fa) {
            depth_er(*it, k, depth[k]);
        }
    }
}

int grand(int k, int len) {
    if(granda[k][len] != -1) {
        return granda[k][len];
    }
    if(1 << len > depth[k]) {
        return 0;
    }
    if(len == 0) {
        granda[k][0] = fa[k];
        return fa[k];
    }
    granda[k][len] = grand(grand(k, len - 1), len - 1);
    return granda[k][len];
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> root;
    for(int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    fa_er(root, 0);
    depth_er(root, 0, -1);
    memset(granda, 0xff, sizeof(granda));
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if(depth[a] < depth[b]) {
            swap(a, b);
        }
        while(depth[a] > depth[b]) {
            a = grand(a, (int)log2(depth[a] - depth[b]));
        }
        if(a == b) {
            cout << a << endl;
            continue;
        }
        for(int j = (int)log2(depth[a]); j > -1; j--) {
            if(grand(a, j) != grand(b, j)) {
                a = grand(a, j);
                b = grand(b, j);
            }
        }
        cout << fa[a] << endl;
    }
    return 0;
}