• 公共祖先问题

函数名解释
deep[i]：i点的深度
fa[i][j]：第i点 上面第2^j的祖先的编号

伪代码

int lca(int x,int y)
{
    if(deep[y]>deep[x])
        swap(x,y);//假设x的深度大于y的深度
    for(int i=20;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y])//利用倍增 使x追上y的深度
            x=fa[x][i];
    if(x==y) return x;//特判
    for(int i=20;i>=0;i--)//x，y 同时向上寻找
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];//返回父亲
}