BOJ. LCA (11437)

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
typedef long long ll;
const int INF = 987654321;

class Node {
  public:
    vector<int> child;
};

int n, k;
vector<Node> nodes(50001);
int parent[50001][17];
int depth[50001];

void dfs(int idx) {
  for(int child: nodes[idx].child) {
    if(child == parent[idx][0]) continue;
    depth[child] = depth[idx] + 1;
    parent[child][0] = idx;
    dfs(child);
  }
}

void calc_sparse() {
  for1(j, 16) {
    for1(i, n) {
      parent[i][j] = parent[parent[i][j-1]][j-1];
    }
  }
}

int lca(int a, int b) {
  if(depth[a] < depth[b]) swap(a, b);
  for(int i = 16; i >= 0; i--) {
    if(depth[a] - depth[b] >= 1<<i) a = parent[a][i];
  }
  if(a == b) return a;
  for(int i = 16; i >= 0; i--) {
    if(parent[a][i] != parent[b][i]) {
      a = parent[a][i];
      b = parent[b][i];
    }
  }
  return parent[a][0];
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  cin >> n;
  for0(i, n-1) {
    int a, b; cin >> a >> b;
    nodes[b].child.push_back(a);
    nodes[a].child.push_back(b);
  }

  dfs(1);
  calc_sparse();
  int m; cin >> m;
  for0(i, m) {
    int a, b; cin >> a >> b;
    cout << lca(a, b) << endl;
  }
  return 0;
}