11438 LCA2

#include <stdio.h>
#include <vector>
#include <math.h>
 
using namespace std;
 
int rst, maxD = (int)log2(100005);
int depth[100005] = { 0 };
int par[100005][100] = { 0 };
int visit[100005] = { 0 };
 
vector<vector<int> > son(100005);
vector<vector<int> > adj(100005);
 
void dfs(int idx);
void lca(int idx1, int idx2);
void generate(int idx);
 
int main() {
    int n, m;
    scanf("%d", &n);
    getchar();
 
    depth[1] = 1;
 
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        getchar();
 
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    generate(1);
 
    scanf("%d", &m);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        lca(a, b);
        printf("%d\n", rst);
    }
    
}
 
void generate(int idx) {
    visit[idx] = 1;
 
    for (int i = 0; i < adj[idx].size(); i++) {
        int x = adj[idx][i];
        if (visit[x] == 0) {
            depth[x] = depth[idx] + 1;
            par[x][0] = idx;
            son[idx].push_back(x);        
 
            for (int j = 1;; j++) {
                if (par[par[x][j-1]][j-1] != 0) {
                    par[x][j] = par[par[x][j - 1]][j - 1];
                }
                else
                    break;
            }
 
            generate(x);
        }
    }
}
 
void lca(int idx1, int idx2) {
    //높이 똑같이 맞춰주는 부분
    if (depth[idx1] < depth[idx2]) {    //swap - idx1 이 더 깊도록
        int tmp = idx2;
        idx2 = idx1;
        idx1 = tmp;
    }
 
    for (int i = maxD; i >= 0; i--) {
        if (depth[par[idx1][i]] >= depth[idx2]) {
            idx1 = par[idx1][i];
        }
    }
 
    //둘중 하나가 조상일때 - lca를 멈춤
    if (idx1 == idx2) {
        rst = idx1;
        return;
    }
    //공통조상 찾는 부분
    int i;
    for (i = maxD; i >= 0 ; i--) {
        if (par[idx1][i] != par[idx2][i]) {
            idx1 = par[idx1][i];
            idx2 = par[idx2][i];
        }
    }
    //결괏값 저장
    rst = par[idx1][0];
}