最近共同祖先(LCA)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=5e5+10;
vector<int> a[N];
int deep[N];
int dp[N][20];
int n,m,s;
void dfs(int u,int fa){
    deep[u]=deep[fa]+1;
    dp[u][0]=fa;
    for(int i=1;(1<<i)<=deep[u];i++){
        dp[u][i]=dp[dp[u][i-1]][i-1];
    }
    for(auto v:a[u]){
        if(v==fa) continue;
        dfs(v,u);
    }
}
int LCA(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=19;i>=0;i--){
        if(deep[x]-(1<<i)>=deep[y]){
            x=dp[x][i];
        }
    }
    if(x==y) return x;
    for(int i=19;i>=0;i--){
        if(dp[x][i]!=dp[y][i]){
            x=dp[x][i],y=dp[y][i];
        }
    }
    return dp[x][0];
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(s,0);
    while(m--){
        int u,v;
        cin>>u>>v;
        cout<<LCA(u,v)<<endl;
    }
    return 0;
}