The beauty of SQRT(N) -- part II

Another good SQRT(N) trick can be applied to Lowest Common Ancestor (LCA) problem.

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 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;