悬关求调

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long l;
l n, m, s, x, y, dep[500005], fa[500005][20], head[500005], cnt(0);

struct Tree {
    l next, to;
} t[1000005];

void add(l x, l y) {
    t[++cnt].next = head[x];
    head[x] = cnt;
    t[cnt].to = y;
}

void dfs(l x, l dad) {
    dep[x] = dep[dad] + 1;
    fa[x][0] = dad;
    for (l i(1); i < 20; ++i) {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (l i(head[x]); i;  i = t[x].next) {
        if (t[i].to != dad) {
            dfs(t[i].to, x);
        }
    }
}

l lca(l x, l y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (l i(16); i >= 0; --i) {
        if (dep[fa[x][i]] >= dep[y]) {
            x = fa[x][i];
        }
    }
    if (y == x) return x;
    for (l i(16); i >= 0; --i) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &s);
    while (--n) {
        scanf("%lld%lld", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(s, 0);
    while (--m > -1) {
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", lca(x, y));
    }
}