// v --> Depth(v)
// logn
int depth( int v )
{
  int dep = (v != root);
  for k = logn..0
    if parent[k, v] != root
      dep += 2^k
      v = parent[k, v]
  return dep;
}

// ---------------> LCA

parent[0, v]
parent[0, root] = root

// 2^k
// Time = nlogn, Memory = nlogn
for k = 1..logn
  for v = 1..n
    parent[k, v] = parent[k-1, parent[k-1, v]]

dfs( int v, int depth )
  dep[v] = depth
  in_time[v] = T++
  ...
  out_time[v] = T++

int is_ancestor( int a, int b )
{
  return in_time[a] <= in_time[b] && out_time[b] <= out_time[a];
}

int LCA( int a, int b )
{
  for k = logn..0
    if (!is_ancestor(parent[k, a], b))
      a = parent[k, a]
  return is_ancestor(a, b) ? a : parent[0, a]
}