记录一发欧拉序和 ST 表求 LCA 的做法。
时间复杂度：预处理 $O(n \log n)$，询问 $O(1)$。

之前一直觉得这东西很难所以不敢学。

首先干出欧拉序，然后发现两个点的 LCA 就是这两个点 dfn 中间深度最小的点。
这玩意儿是个 RMQ 问题，所以可以用线段树维护。

显然 RMQ 要支持更快速的查询需要使用 ST 表。这样可以做到 $O(1)$ 查询区间最小值。
于是这题就做完了。

//by_Conan15
//欧拉序+ST表 O(1) 求 LCA
//记得是欧拉序所以要开两倍。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 15, M = N << 1;
int n, q, rt;
int h[N], e[M], ne[M], idx = 0;
int dep[N], dfn[N];
int up[M][25], lg[M], tot = 0;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int father) {
    up[++tot][0] = u, dfn[u] = tot;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == father) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        up[++tot][0] = u;
    }
}

int get(int u, int v) {
    if (dep[u] < dep[v]) return u;
    return v;
}
void init() {
    lg[1] = 0;
    for (int i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= tot; j++) {
            if (j + (1 << i) - 1 > tot) break;
            up[j][i] = get(up[j][i - 1], up[j + (1 << i - 1)][i - 1]);
        }
    }
}
int mn(int l, int r) {
    if (l > r) swap(l, r);
    int len = lg[r - l + 1];
    return get(up[l][len], up[r - (1 << len) + 1][len]);
}

int lca(int u, int v) {
    return mn(dfn[u], dfn[v]);
}

int main() {
    scanf("%d%d%d", &n, &q, &rt);
    for (int i = 1; i <= n; i++) h[i] = -1;
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(rt, 0);
    init();
    while (q--) {
        int u, v; scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

经测试，树剖在本题中跑得最快，常数巨小。