11437 LCA

#include <stdio.h>
#include <vector>
#include <math.h>
 
using namespace std;
 
int depth[50005] = { 0 };
int par[50005][30] = { 0 };
int visit[50005] = { 0 };
int rst;
 
vector<vector<int> > son(50005);
vector<vector<int> > adj(50005);
 
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
        int tmp = idx2;
        idx2 = idx1;
        idx1 = tmp;
    }
 
    int len = depth[idx1] - depth[idx2], iter;
    if (len != 0) {
        iter = (int)log2(len);
        idx1 = par[idx1][iter];
    }
    else
        iter = 0;
    
    while (depth[idx1] != depth[idx2]) {
        idx1 = par[idx1][0];
    }
 
    //둘중 하나가 조상일때 - lca를 멈춤
    if (idx1 == idx2) {
        rst = idx1;
        return;
    }
 
    //공통조상 찾는 부분
    int i;
    for (i = 0; ; i++) {
        if (par[idx1][i] == par[idx2][i]) {
            break;
        }
    }
 
    if (i != 0) {
        idx1 = par[idx1][i - 1];
        idx2 = par[idx2][i - 1];
    }
 
    while (idx1 != idx2) {
        idx1 = par[idx1][0];
        idx2 = par[idx2][0];
    }
 
    //결괏값 저장
    rst = idx1;
}