自带两倍常数求救

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mpr make_pair
#define ld double
#define sdn cout
#define vi vector<int>
#define ull unsigned long long
#define fi first
#define se second
#define pii pair<int,int>
mt19937_64 rnd(time(nullptr));

const int N = 2e6 + 10,M = 1e6 + 10,INF1 = 1e9 + 7;
const ll INF2 = 1e18 + 7,MOD = 998244353;
const ull base = 131;

int n,m,k,q,T,rt,a[N],dfn[N],id[N],f[N],tp[N],siz[N],bson[N],dep[N],cnt;
vi lk[N];
ll ans;
void dfs1(int u,int fa){
    siz[u] = 1;f[u] = fa;
    dep[u] = dep[fa] + 1;
    for(auto v : lk[u]){
        if(v == fa)  continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(!bson[u] || siz[v] > siz[bson[u]])  bson[u] = v;
    }
}
void dfs2(int u,int fa,int top){
    tp[u] = top;
    dfn[u] = ++cnt;
    id[cnt] = u;
    if(bson[u])  dfs2(bson[u],u,top);
    for(auto v : lk[u]){
        if(v == fa || v == bson[u])  continue;
        dfs2(v,u,v);
    }
}
int lca(int x,int y){
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]])  swap(x,y);
        x = f[tp[x]];
    }
    return id[dfn[dep[x]>dep[y]?y:x]];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m>>rt;
    for(int i = 1;i < n;i ++){
        int u,v;cin>>u>>v;
        lk[u].pb(v),lk[v].pb(u);
    }
    dfs1(rt,rt);
    dfs2(rt,0,rt);
    for(int i = 1;i <= m;i ++){
        int x,y;cin>>x>>y;
        sdn<<lca(x,y)<<endl;
    }
    return 0;
}