题解

广搜+ST表

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=5e5+5;
vector<int>e[N];
int dep[N];
int f[N][20],n,m,s;
void makefather(){
    queue<int>q;
    f[s][0]=s;
    //用广搜，去找到每个节点的爹，并且可以更好更新深度
    dep[s]=1;
    q.push(s);
    while(q.size()){
        int temp=q.front();
        q.pop();
        for(auto i:e[temp]){
            if(!f[i][0]){
                f[i][0]=temp;//认祖归宗
                dep[i]=dep[temp]+1;//儿子辈分比爹小（深度为父节点+1）
                q.push(i);
            }
        }
    }
}
void ST(){
    for(int j=1;j<20;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
            //4 节点 跳2^3  =4节点先跳2^2，再跳2^2
}
int lca(int x,int y){
    if(dep[y]>dep[x])swap(x,y);//调整深度
    int t=dep[x]-dep[y],cnt=0;
    while(t){
        if(t%2)x=f[x][cnt];
        cnt++;
        t/=2;
    }
    if(x==y)return x;
    int maxstep=19;
    for(int i=maxstep;i>=0;i--)//循环找到lca的儿子
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    x=f[x][0];
    y=f[y][0];
    return x;
}
void solve(){
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<"\n";
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    //建立父节点
    makefather();
    ST();
    //输出
    solve();
    return 0;
}