求助，dfs序+ST表wa0

//problem: P3379 【模板】最近公共祖先（LCA） 
//date: 2023.11.8-16:29
#include <bits/stdc++.h>
#define int long long
#define FH signed
using namespace std;

const int N = 5e5 + 10;

vector<int> e[N];

int f[N][30], fa[N];

int cnt = 0, dfn[N];

void dfs(int u, int ff)
{
    f[++ cnt][0] = u;
    dfn[u] = cnt; fa[u] = ff;
    for(auto v : e[u])
    {
        if(v == ff) continue;
        dfs(v, u);
    }
}

int lg[N];

int get(int x, int y)
{
    return (dfn[x] < dfn[y]) ? x : y;
}

FH main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, s;
    cin >> n >> m >> s;

    for(int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    dfs(s, 0);

    for(int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1;

    for(int j = 1; j <= lg[n]; j ++)
        for(int i = 1; i <= n - (1 << j) + 1; i ++)
            f[i][j] = get(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    
    // for(int i = 1; i <= cnt; i ++) cout << f[i][0].id << " " << f[i][0].val << "~~\n";
    
    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;
        if(a == b) {cout << a << "\n"; continue;}
        if((a = dfn[a]) > (b = dfn[b])) swap(a, b);
        a ++; int k = lg[b - a + 1];
        // cout << k << "\n";
        cout << fa[get(f[a][k], f[b - (1 << k) + 1][k])] << "\n";
    }
    
    return 0;
}