(백준 알고리즘 문제풀이) 11437번 LCA

#include <queue>
#include <vector>
#include <cstdio>
#define INF 1000000000

using namespace std;

vector<vector<int> > ll;
int parent[17][50020], level[50020];
int n, m, v, w, u;

int LCA(int chd, int par){
    int diff = level[chd] - level[par];
    for(int i = 16; i >= 0; i--){
        if((1<<i) <= diff){
            chd = parent[i][chd];
            diff -= (1<<i);
        }
    }
    if(chd == par) return chd;
    for(int i = 16; i >= 0; i--){
        if(parent[i][chd] != parent[i][par]){
            chd = parent[i][chd];
            par = parent[i][par];
        } 
    } 
    return parent[0][chd];
}

void build_tree(){
    queue<int> q;
    level[1] = 1, parent[0][1] = 1;
    q.push(1);
    while(!q.empty()){
        u = q.front(); q.pop();
        for(int i = 0; i < ll[u].size(); i++){
            v = ll[u][i];
            if(level[v] == 0){
                level[v] = level[u] + 1;
                parent[0][v] = u;
                q.push(v);
            }
        }
    }
}
void find_parent(){
    for(int i = 1; i < 17; i++){
        for(int j = 1; j < n + 1; j++)parent[i][j] = parent[i-1][parent[i-1][j]];
    }
}

int main(){
    scanf("%d", &n);
    ll = vector<vector<int> >(n + 1);
    for(int i = 1; i < n; i++){
        scanf("%d %d", &v, &u);
        ll[v].push_back(u);
        ll[u].push_back(v);
    }
    build_tree();
    find_parent();

    m = readInt();
    while(m--){
        scanf("%d %d", &v, &u);
        printf("%d\n", level[v] > level[u] ? LCA(v, u) : LCA(u, v));       
    }
}