lca2

#include <iostream>
#include <vector>
#include <queue>
 
#define MAXX 100001 
using namespace std;
 
int p[21][MAXX];
vector<int> edges[MAXX];
bool visited[MAXX];
int depth[MAXX];
 
void bfs() {
    queue<int> q;
 
    q.push(1);
    visited[1] = 1;
    depth[1] = 1;
 
    while(!q.empty()) {
        int now = q.front();
        q.pop();
 
        for (auto i : edges[now]) {
            if (!visited[i]) {
                visited[i] = true;
                depth[i] = depth[now] + 1;
                //now의 자식이므로 depth를 늘려준다. 
                p[0][i] = now;
                q.push(i);
            }
        }
    }
}
void setParent(int n) {
    for (int i = 1; i < 21; i++) {
        for (int j = 1; j <= n; j++) {
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }
    cout << "debug parent"<< '\n';
    for (int i = 0; i < 21; i++) {
        for (int j = 1; j <= n; j++) {
            cout << p[i][j] << ' ';
        }
        cout << '\n';
    }
    cout << "end debug" << '\n';
}
int lca(int a, int b) {
    //a의 depth가 덜 깊도록 설정한다. 
    if (depth[a] > depth[b]) {
        int tmp = a;
        a = b;
        b = tmp;
    }
 
    //depth를 맞춰준다. 
    int i = 20;
 
    while(i>= 0) {
        if (depth[b] - depth[a] >= (1<<i) ) {
            b = p[i][b];
        }
        i--; //부모부모의 부모부모로 올라간다
    }
 
    if (a == b) return a; //a는 b의 조상 
 
    i = 20;
    while (i >= 0) {
        if (p[i][a] != p[i][b]) {
            a = p[i][a];
            b = p[i][b];
        }
        i--;
    }
 
    return p[0][a];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    //노드의 개수, 쿼리의 개수
    cin >> n;
 
    for (int i = 0; i < n-1; i++) {
        //간선의 개수는 노드의 개수 -1 
        int a, b;
        cin >> a >> b;
 
        edges[a].push_back(b);
        edges[b].push_back(a);
        
    }
 
    bfs(); //트리 전처리 
    setParent(n);
    
    cin >> m;
 
    while(m--) {
        int a, b;
        cin >> a >> b;
 
        cout << lca(a, b) << '\n';
    }
 
    return 0;
}