Cube Root Decomp

list<int> adj[max_v];
int par[max_v], dep[max_v], sup[max_v], dup[max_v];
int n, q;
void dfs(int u, int p, int d){

  par[u] = p;
  dep[u] = d;
  for(int v : adj[u])
    if(v != p)
      dfs(v, u, d + 1);
}

void precomp(){
  for(int i = 1, j; i<=n; i++)
    for(j = 0, sup[i] = i; sup[i] && j < CUBE; j++) sup[i] = par[sup[i]];
  for(int i = 1, j; i<=n; i++)
    for(j = 0, dup[i] = i; dup[i] && j < CUBE; j++) dup[i] = sup[dup[i]];
}

int k_up(int u, int k){
  for(; k >= CUBE * CUBE; k -= CUBE * CUBE) u = dup[u];
  for(; k >= CUBE; k -= CUBE) u = sup[u];
  for(; k; k--) u = par[u];
  return u;
}

int lca(int u, int v){
  if(dep[u] < dep[v]) swap(u, v);
  u = k_up(u, dep[u] - dep[v]);
  while(dup[u] != dup[v]) u = dup[u], v = dup[v];
  while(sup[u] != sup[v]) u = sup[u], v = sup[v];
  while(u != v) u = par[u], v = par[v];
  assert(u == v && v);
  return u;
}