LCA cu RMQ

const int NMAX = 2e5 + 5; /// 2 * N
int N, M, tour[NMAX], depth[NMAX], first[NMAX], lg2[NMAX], rmq[20][NMAX];
vector<int> G[NMAX];

void dfs_Euler(int u, int parent, int level) {
  sz[u] = 1;
  tour[++M] = u;
  depth[M] = level;
  first[u] = M;
  for (int v : G[u])
    if (v != parent) {
      dfs_Euler(v, u, level + 1);
      sz[u] += sz[v];
      tour[++M] = u;
      depth[M] = level;
    }
}

void compute_rmq() {
  for (int i = 2; i <= M; ++i)
    lg2[i] = lg2[i >> 1] + 1;
  for (int i = 1; i <= M; ++i)
    rmq[0][i] = i;
  for (int i = 1; (1 << i) < M; ++i)
    for (int j = 1; j <= M - (1 << i); ++j) {
      int l = 1 << (i - 1);
      rmq[i][j] = rmq[i - 1][j];
      if (depth[rmq[i - 1][j + l]] < depth[rmq[i][j]])
        rmq[i][j] = rmq[i - 1][j + l];
    }
}

int lca(int u, int v) {
  int x = first[u], y = first[v];
  if (x > y)
    swap(x, y);
  int diff = y - x + 1;
  int l = lg2[diff];
  int sol = rmq[l][x];
  int shift = diff - (1 << l);
  if (depth[sol] > depth[rmq[l][x + shift]])
    sol = rmq[l][x + shift];
  return tour[sol];
}

int dist(int u, int v) {
  return depth[first[u]] + depth[first[v]] - (depth[first[lca(u, v)]] << 1);
}