sqrt lca

#include <iostream>
using namespace std;
const int R = 330, MX = 1e5 +10;
vector<int> adj[MX];
int dep[MX], par[MX], super[MX], 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);
    }
}
//note this lca implementation is in 1-based indexing
//so node 0 is "parent" of the root
void precomp(){
    for(int i = 1; i<=n; i++){
        super[i] = i;
        for(int j = 0; j<R && super[i] != 0; j++) super[i] = par[super[i]];
    }
}

int k_up(int u, int k){
   while(k >= R) k = k/R, u = super[u];
   for(int i = 0; i<k; i++) u = par[u];
   return 0;
}

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

int main(){
    cin >> n;
    for(int i = 1; i<n; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1, 0, 0);
    precomp();
    while(q--){
        int a, b; cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}