两种LCA写法,前者不对后者对,但前者是我平常的写法一直没错过,为啥?
int lca(int x,int y)
{
if(dep[x]>dep[y])
swap(x,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);
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];
}