**LCA**

This problem consists in identifying the lowest common ancestor given two nodes in a tree. One way is to split the tree vertically in SQRT(H) parts, where H is height of the tree. So for each part, we should store the ancestor situated in the part immediately above. That is easy because the ancestor for each border section is the father of the section (e.g. the node at the frontier).

So assume that the node i, has father F[i], we can pre-compute an array P [1..N] as it follows

if (i is at first level) P[i] = 1 // first level

else if (i is at the border of one of the SQRT(H) partitions than P[i] = F[i]) // border

else (P[i] = P [ F[ i] ]) // any other node

So we have SQRT(H) partitions and the pre computation is linear. We use P for reducing the cost of LCA to SQRT(H) as it follows

while(P[x] != P[y]) // different sectionif(L[x] > L[y]) // up with the longest x = P[x]; // up one sectionelsey = P[y]; // up one sectionwhile(x != y) // same sectionif(L[x] > L[y]) // up with the longest x = F[x]; // take the fatherelsey = F[y];returnx;

## No comments:

## Post a Comment