nth root lca

const int max_v = ;
const int RT = , LOG = ; //RT^LOG approx max_v
vector<int> adj[max_v];
int super[max_v][LOG * 2], par[max_v], dep[max_v], base[max_v], n, q;

void dfs(int u, int p, int d){ //general util dfs
  par[u] = super[u][0] = p;
  dep[u] = d;
  for(int v : adj[u])
    if(v != p)
       dfs(v, u, d + 1);
}

void precomp(){
  base[0] = 1;
  for(int k = 1; k<=LOG; k++){
    base[k] = base[k - 1] * RT;
    for(int i = 1, j; i<=n; i++){
      for(j = 0, super[i][k] = i; j < RT && super[i][k]; j++){
        super[i][k] = super[super[i][k]][k - 1];
      }
    }
  }
}

int k_up(int u, int k){
  for(int i = LOG; i >= 0; i--){
    while(k >= base[i])k -= base[i], u = super[u][i];
  }
  return u;
}

int LCA(int u, int v){
  if(dep[u] < dep[v]) swap(u, v);
  u = k_up(u, dep[u] - dep[v]);
  if(u == v) return u;
  for(int i = LOG; i >= 0; i--){
    while(super[u][i] != super[v][i]) u = super[u][i], v = super[v][i];
  }
  return (par[u]) ? par[u] : u; //cant return 0
}