https://www.luogu.com.cn/problem/P3379

#include<bits/stdc++.h>
using namespace std;

const int N=500005;
int n,m,s;
vector<int> e[N];
int dep[N];         //i节点的深度
int fa[N][22];      //fa[x][k]表示x的2^k倍祖先

void dfs(int x,int f){ //树增dep,fa 预处理
    dep[x]=dep[f]+1; fa[x][0]=f;
    //cout<<x<<" "<<0<<" "<<fa[x][0]<<'\n';
    //x上面2,4,8...的祖先fa
    for(int i=1; i<=20; i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        //cout<<x<<" "<<i<<" "<<fa[x][i]<<'\n';
    }

    for(int y : e[x])
    {
        if(y!=f) dfs(y,x);
    }

}
int lca(int x,int y){ //树增lca
    if(dep[x]<dep[y]) swap(x,y);
    //x先大步后小步向上跳，直到与y同层
    // dep[x]-dep[y]
    for(int i=20; i>=0; i--)    //从大到小枚举
    {
        if(dep[fa[x][i]]>=dep[y]) 
        {
            x=fa[x][i];
        }
    }
    //x和y跳在同一层
    if(x==y) return y;  //两个点是同一个点
    //x,y同时向上跳，直到lca的下面
    for(int i=20; i>=0; i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i],y=fa[y][i];
        }
    }
    return fa[x][0];//lca的下面节点的父节点就是lca
}
int main(){
    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);   //s是根节点
    while(m--)
    {
      int x,y; cin>>x>>y;
      cout<<lca(x,y)<<'\n';
    }

}