LCA的问题在哪?
查看原帖
LCA的问题在哪?
856309
oiyang楼主2023/10/3 10:41

两种LCA写法,前者不对后者对,但前者是我平常的写法一直没错过,为啥?

int lca(int x,int y)
{
    if(dep[x]>dep[y])
        swap(x,y);//deeper y
    int temp=dep[y]-dep[x];
    for(int i=21;i>=0;i--)
        if(temp &(1<<i))
            y=fa[y][i];
    if(y==x)
        return x;
    for(int i=21;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int lca(int x,int y)
{
    if(dep[x]>dep[y])
        swap(x,y);//deeper y
    for(int i=21;i>=0;i--)
        if(dep[fa[y][i]]>=dep[x])
            y=fa[y][i];
    for(int i=21;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
2023/10/3 10:41
加载中...