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 section if (L[x] > L[y]) // up with the longest x = P[x]; // up one section else y = P[y]; // up one section while (x != y) // same section if (L[x] > L[y]) // up with the longest x = F[x]; // take the father else y = F[y]; return x;