倍增LCA模板2董博文版 伪代码

Dfs(int rt){
    f[0][rt];
    for(int k=1;k<=20;k++)
        f[k][rt]=f[k-1][f[k-1][rt]];

}

int LCA(int x,int y){
    if(Dp[x]<Dp[y])swap(x,y);
    int res=Dp[x]-Dp[y];
    for(int k=20;k>=0;k--)
        if((1<<k)<=res)x=f[k][x],res-=1<<k;
    if(x==y)return x;
    for(int k=20;k>=0;k--){
        if(f[k][x]!=f[k][y])
            x=f[k][x],y=f[k][y];
    }
    return f[0][x];
}