采用倍增的方法 求LCA

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,tot;
int net[200010],to[200010],head[200010];
int deep[200010],f[200010][30];
int ru[200010];
void add(int x,int y)
{
    net[++tot]=head[x];
    to[tot]=y;
    head[x]=tot;
}
void dfs(int x,int temp)
{
    f[x][0]=temp;
    deep[x]=deep[temp]+1;
    for(int i=1;f[x][i-1];i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x];i;i=net[i])
        if(to[i]!=temp)dfs(to[i],x);
}
void Swp(int &x,int &y)
{
    int tmp=x;
    x=y;y=tmp;
    return;
}
int find(int x,int y)
{
    if(deep[x]<deep[y])Swp(x,y);
    int temp=20;
    while(temp>=0)
    {
        if(deep[f[x][temp]]>=deep[y])
            x=f[x][temp];
        temp--;
    }
    if(x==y)return x;
    temp=20;
    while(temp>=0)
    {
        if(f[x][temp]!=f[y][temp])
            x=f[x][temp],y=f[y][temp];
        temp--;
    }
    return f[x][0];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int fa,son;
        scanf("%d%d",&fa,&son);
        add(fa,son),add(son,fa);
        ru[son]++;
    }
    for(int i=1;i<=n;i++)
        if(!ru[i])
        {
            dfs(i,0);
            break;
        }
    for(int i=1;i<=m;i++)
    {
        int dx,dy;
        scanf("%d%d",&dx,&dy);
        printf("%d\n",find(dx,dy));
    }
}