BSOJ1620 -- 【LCA练习】最近公共祖先(版本2)3587

#include<bits/stdc++.h>
using namespace std;
#define why 200005
struct starr
{
    int next,to;
}a[why<<1];
int n,root,p[why][18],d[why],prt[why],h[why],cnt;
void add(int x,int y)
{
    cnt++;
    a[cnt].to=y;
    a[cnt].next=h[x];
    h[x]=cnt;
}
void DFS(int x,int num)
{
    d[x]=num;
    for(int u=h[x];u;u=a[u].next)
    {
        int y=a[u].to;
        DFS(y,num+1);
    }
}
void ST()
{
    for(int i=1;i<=n;i++)p[i][0]=prt[i];
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(p[i][j-1]==-1)continue;
            p[i][j]=p[p[i][j-1]][j-1];
        }
    }
}
int LCA(int L,int R)
{
    int k;
    if(L==R)return L;
    if(d[L]<d[R])swap(L,R);
    k=int(log(d[L])/log(2));//k=log2(d[L]);用log（）代替log2,c++自带log2函数效率不高
    for(int i=k;i>=0;i--)
    {
        if(d[L]-(1<<i)>d[R])L=p[L][i];
        else if(d[L]-(1<<i)==d[R])
        {
            L=p[L][i];
            break;
        }
    }
    if(L==R)return L;
    for(int i=k;i>=0;i--)
    {
        if(p[L][i]!=-1&&p[L][i]!=p[R][i])
        {
            L=p[L][i];
            R=p[R][i];
        }
    }
    return p[L][0];
}
int main()
{
    int _1,_2;
    scanf("%d",&n);
    memset(p,-1,sizeof(p));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&_1,&_2);
        prt[_2]=_1;
        add(_1,_2);
        if(i==1||_2==root)root=_1;
    }
    DFS(root,1);
    ST();
    scanf("%d%d",&_1,&_2);
    printf("%d",LCA(_1,_2));
    return 0;
}