分析

LCA 就是求两个点的最近公共祖先，用倍增的思想，现预处理一下节点走到的地方，然后再求lca

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=5e5+10;
int fa[N][21],he[3*N],ne[3*N],to[3*N];
int dep[N];
int dex;
void add(int x,int y)
{
    ++dex;
    ne[dex]=he[x];
    to[dex]=y;
    he[x]=dex;
}
void dfs(int x,int pre)//预处理
{
    dep[x]=dep[pre]+1;
    fa[x][0]=pre;

    for(int i=1;i<=20;i++)
    fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=he[x];i;i=ne[i])
    {
        int j=to[i];
        if(j!=pre) dfs(j,x);
    }
}
int lca(int x,int y)//lca
{
    if(dep[x]<dep[y])
    swap(x,y);
    while(dep[x]>dep[y]){
         x = fa[x][(int)log2(dep[x] - dep[y])];
    }
    if(x==y) return x;
    for(int j=20;j>=0;j--)
    {
        if(fa[x][j]!=fa[y][j])
            x=fa[x][j],y=fa[y][j];
    }
    return fa[x][0];
}
signed main( )
{
    int n,m,s;
    int root;
    cin>>n>>m>>s;
    int t=n-1;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
            add(x,y);
            add(y,x);
    }
    dfs(s,0);
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
}