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

w[0, v] = weight of edge from v into parent
parent[0, v]

w[0, root] = +infinity
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]]
    w[k, v] = min(w[k-1, parent[k-1, v]], w[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 MIN( int a, int b )
{
  int res = +infinity;
  for k = logn..0
    if !is_ancestor(parent[k, a], b)
      res = min(res, w[k, a])
      a = parent[k, a]
  if !is_ancestor(a, b)
    res = min(res, w[0, a])
    a = parent[0, a]
  // a <--- LCA
  for k = logn..0
    if is_ancestor(a, b)
      res = min(res, w[k, b])
      a = parent[k, b]
  if a != b
    res = min(res, w[0, b])
    a = parent[0, b]
  return res
}

int go( int a, int x )
{
  int res = +infinity;
  for k = logn..0
    if (1 << k) <= dep[x] - dep[a]
      res = min(res, w[k, a])
      a = parent[k, a]
  return res;
}

int MIN_2( int a, int b )
{
  int x = LCA(a, b)
  return min(go(a, x), go(b, x))
}