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 ....
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
at the beginning, but instead compared values of x and y — and this comparison does not makes much sense for me.