11437 LCA

LCA를 찾는 문제.

루트에서 bfs 혹은 dfs를 돌려 모든 node에 대해서 루트로부터의 depth를 구해놓는다.

a,b를 입력받으면 각각의 depth를 보고 일단 depth를 맞춘다. depth가 깊은쪽에서 depth 차이만큼 parent를 찾아가게 하면 된다.

이제는 양쪽에서 depth를 줄여가면서 parent를 찾다보면 같아지게 되는 때가 있는데 그게 LCA다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int d[50001], p[50001], n, u, v, m;
vector<int> adj[50001];
void bfs() {
    queue<int> q;
    d[1] = 1;
    q.push(1);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (auto i : adj[x]) {
            if (d[i]) continue;
            q.push(i);
            d[i] = d[x] + 1;
            p[i] = x;
        }
    }
}
 
int main() {
    scanf("%d", &n);
    n--;
    while (n--) {
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs();
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d", &u, &v);
        while (d[u] < d[v]) 
            v = p[v];
        while (d[v] < d[u]) 
            u = p[u];
        while (u != v) {
            v = p[v];
            u = p[u];
        }
        printf("%d\n", u);
    }
    
    return 0;
}