题解 | 【模板】最近公共祖先（LCA）

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>p[N];
int fa[N][25],deep[N];
void dfs(int x,int f)
{
    fa[x][0]=f;
    for(int i=1;i<25;i++)
    {
        fa[x][i]=fa[f][i-1];
    }
    deep[x]=deep[f]+1;
    for(auto&pair:p[x])
    {
        if(pair==f)continue;
        dfs(pair,x);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    for(int i=24;i>=0;i--)
    {
        if(deep[fa[x][i]]>=deep[y])
        {
            x=fa[x][i];
        }
    }
    if(x==y)return x;
    for(int i=24;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
void solve()
{
    int n,m,r;
    cin>>n>>m>>r;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        p[u].push_back(v);
        p[v].push_back(u);
    }
    deep[0]=0;
    dfs(r,0);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<"\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t__=1;
    //cin>>t__;
    while(t__--)
    {
        solve();
    }
    return 0;
}