倍增求LCA 70pts求条

#include<bits/stdc++.h>
using namespace std;
const int MaxN=5e5;

int head[MaxN+5],Next[2*MaxN+5],to[2*MaxN+5],dep[MaxN+5];
int fno[MaxN][25];
int cnt;

void add(int x,int y)
{
    Next[++cnt]=head[x];
    to[cnt]=y;
    head[x]=cnt;
}

int dfs(int n,int f)//n为当前节点编号 f为父亲编号
{
    fno[n][0]=f;//认父亲
    dep[n]=dep[f]+1;
    for(int i=1;i<=21;++i)fno[n][i]=fno[fno[n][i-1]][i-1];//倍增
    for(int i=head[n];i;i=Next[i])//递归子节点
    {
        if(to[i]!=f)//排除父亲
        {
            dfs(to[i],n);
        }
    }
    return 0;
}

int lca(int x,int y)
{
    if(x==y)return x;
    if(dep[x]<dep[y])swap(x,y);//使得x更深
    for(int trip=21;trip>=0;trip--)//调整到同一深度
    {
        if(dep[fno[x][trip]]>=dep[y])x=fno[x][trip];
    }
    if(x==y)return x;
    for(int trip=21;trip>=0;trip--)//倍增
    {
        if(fno[x][trip]==fno[y][trip])continue;
        x=fno[x][trip],y=fno[y][trip];
    }
    return fno[x][0];
}

int main()
{
    int n,m,root;
    scanf("%d %d %d",&n,&m,&root);
    --n;
    while(n--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b); add(b,a);
    }

    dfs(root,0);
    fno[root][0]=0;
    
    while(m--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}