راه حل O(n+q*lg(n)) به کمک جداسازی سبک-سنگین¶

#include<bits/stdc++.h>

using namespace std;

const int M = 1e5+5;

int edge_counter = 1;

int st[M], stp[M], hld[M], par[M], h[M];
vector<int> g[M];
int time = 0;

int dfsz(int x, int p = 0) {
  int sz = 1, mxsz = -2;
  if (p == g[x][0]) swap(g[x][0], g[x][g[x].size()-1]);
  for (int i = 0; i < g[x].size(); i++) {
    if (g[x][i] == p) continue;
    int szy = dfsz(g[x][i], x);
    sz += szy;
    if (szy > mxsz) {
      mxsz = szy;
      swap(g[x][0], g[x][i]); // enteghale yal sangin be g[x][0]
    }
  }
  return sz;
}

void dfst(int stpx, int p = 0) {
  int x = st[stpx] = time++; // shomare ras ha ra joori avaz mikonim ke yal haye sangin
  stp[x] = stpx; // motevali bashand. in jayghasht ra dar st[x] va barakse aan ra dar stp[x] mirizim
  for (int stpy: g[stpx]) {
    if (stpy == p) continue;
    dfst(stpy, stpx);
    par[st[stpy]] = x;
  }
}

int parat(int stpx, int hgoal) { // jadi az rase voroodi ke ertefae hadaf ra darad ra mikhahim
  int x = hld[st[stpx]];
  while (h[x] > hgoal) x = hld[par[x]];
  return stp[x + hgoal - h[x]];
}

int main(){
  // derakht ra voroodi begirid va yal ha ra dar g berizid
  dfsz(0);
  dfst(0);
  for (int x = 1; x < n; x++) {
    h[x] = h[par[x]] + 1;
    hld[x] = par[x] == x - 1 ? hld[x-1] : x; // hld[x] bala tarin jadi ast ke be aan yale sangin darim
  }
  // sepas porsesh ha ra ba parat pasokh dahid
}

const int M = 1e5+5;

int edge_counter = 1;

int st[M], stp[M], hld[M], par[M], h[M];
vector <int> g[M];
int time = 0;

int dfsz(int x, int p = 0) {
  int sz = 1, mxsz = -2;
  if (p == g[x][0]) swap(g[x][0], g[x][g[x].size() - 1]);
  for (int i = 0; i < g[x].size(); i++) {
    if (g[x][i] == p) continue;
    int szy = dfsz(g[x][i], x);
    sz += szy;
    if (szy > mxsz) {
      mxsz = szy;
      swap(g[x][0], g[x][i]); // enteghale yal sangin be g[x][0]
    }
  }
  return sz;
}

void dfst(int stpx, int p = 0) {
  int x = st[stpx] = time++; // shomare ras ha ra joori avaz mikonim ke yal haye sangin
  stp[x] = stpx; // motevali bashand. in jayghasht ra dar st[x] va barakse aan ra dar stp[x] mirizim
  for (int stpy: g[stpx]) {
    if (stpy == p) continue;
    dfst(stpy, stpx);
    par[st[stpy]] = x;
  }
}

int parat(int x, int hgoal) { // jadi az rase voroodi ke ertefae hadaf ra darad ra mikhahim
  int x = hld[x];
  while (h[x] > hgoal) x = hld[par[x]];
  return x + hgoal - h[x];
}

int lca(int stpx, int stpy) {
  int x = st[stpx], y = st[stpy];
  if (h[x] < h[y]) swap(x,y);
  x = parat(x, h[y]); // do ras ra ham ertefa mikonim ta kod sade tar shavad
  while (x != y) {
    x = hld[x];
    y = hld[y];
    if (h[x] < h[y]) swap(x, y);
    y += h[x] - h[y];
    x = par[x];
    y = par[y];
  }
  return stp[x];
}

int main(){
  // derakht ra voroodi begirid va yal ha ra dar g berizid
  dfsz(0);
  dfst(0);
  for (int x = 1; x < n; x++) {
    h[x] = h[par[x]] + 1;
    hld[x] = par[x] == x - 1 ? hld[x-1] : x; // hld[x] bala tarin jadi ast ke be aan yale sangin darim
  }
  // sepas porsesh ha ra ba parat pasokh dahid
}