NeverSayNever's blog

By NeverSayNever, 9 years ago, In English

Hello everyone, I was reading how to find LCA lowest common Ancestor using DP so that each of type LCA(x,y) can be handled in log(n)

int _getlca(int x,int y){

if(y>x)
    swap(x,y);
for(int i=16;i>=0;i--){
    if(pa[x][i]!=-1 && L[pa[x][i]] >= L[y])
       x = pa[x][i];
}
if(x==y)
    return x;
assert(L[x]==L[y]); /*here ... */
for(int i=16;i>=0;i--){
    if(pa[x][i]!=-1 && pa[x][i]!=pa[y][i]){
       x = pa[x][i],pa[y][i];
    }
}
return P[x];

}

Here is the code .. Checkout the assert condition in this code . I put that condition because i thought at this step Level or depth of both the nodes must be equal . But this is not true can anybody provide me any test case for this ....

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about case when L[x]<L[y]?

Vertices are enumerated in such way that vertex with larger number never has smaller depth? If no — then i guess you wanted to put something like

if (L[y]>L[x])

at the beginning, but instead compared values of x and y — and this comparison does not makes much sense for me.