LCA[模板]

#include <bits/stdc++.h>
#define int long long
#define MAXN 500010
using namespace std;
struct edge
{
    int nxt,to;
};
edge e[MAXN*2];
int h[MAXN],ei;
void add(int x,int y){
    ei++;
    e[ei].to = y;
    e[ei].nxt = h[x];
    h[x] = ei;
}
int u[MAXN], f[MAXN][20],dep[MAXN],lg[MAXN],n,m,s;
void dfs(int s)
{
    u[s] =1;
    //建立倍增
    for(int i=1;i<=19;i++){
        int t1 = f[s][i-1]; //2^i  2
        if(t1==0) break;
        int t2 = f[t1][i-1];
        if(t2==0) break; 
        f[s][i] = t2;
    }
    for(int i=h[s];i;i=e[i].nxt){
        int to = e[i].to;
        if(u[to]==1) continue;
        dep[to] =dep[s]+1;
        f[to][0] = s; //to 爬2^0是 s 
        dfs(to);
    }
}
int climb(int x,int l){
    while(l!=0){
        int p  = lg[l];
        x = f[x][p];
        l = l - (1<<p); 
    }
    return x;
}
void buildlg2(){
    lg[1] = 0;
    for(int i=2;i<=n;i++) lg[i] = lg[i/2]+1;
}
int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }//
    x = climb(x,dep[x]-dep[y]);
    if(x==y) return x;
    int l = 1,r = dep[x];//白和 
    while(l<r)
    {
        int mid=(l+r)>>1;
        int fx = climb(x,mid);
        int fy = climb(y,mid);
        if(fx==fy){
            r = mid;
        }else{
            l = mid+1;
        }
    } 
    return climb(x,r);
}
signed main()
{
    cin>>n>>m>>s;
    buildlg2();
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);
        add(y,x);
    }
    dep[s] =1;
    dfs(s);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%lld%lld",&x,&y); 
        printf("%lld\n",lca(x,y));
    }
    return 0;
}