BOJ 3584 가장 가까운 공통 조상

1 개요[ | ]

BOJ 3584 가장 가까운 공통 조상
2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

int N, node1, node2;
vector<int> graph[10001];
bool chk[10001];
int depth[10001];
int parent[10001][15];

void dfs(int v, int d) {
    depth[v] = d;
    for (int i=0; i<graph[v].size(); i++) {
        int next = graph[v][i];
        if (depth[next]) continue;
        parent[next][0] = v;
        dfs(next, d+1);
    }
}
 
int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int i=14; i>=0; i--) {
        if (depth[v]-depth[u] >= (1 << i)) {
            v = parent[v][i];
        }
    }
    if (u == v) return u;
    for (int i=14; i>=0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[v][0];
}

void solve() {
    int root;
    for (int i=1; i<=N; i++) {
        if (!chk[i]) {
            root = i;
            break;
        }
    }
    dfs(root, 1);
    for (int j=1; j<15; j++) {
        for (int i=1; i<=N; i++) {
            parent[i][j] = parent[parent[i][j-1]][j-1];
        }
    }
    cout << lca(node1, node2) << '\n';
}

void sub() {
    memset(depth, 0, sizeof(depth));
    memset(parent, 0, sizeof(parent));
    memset(chk, false, sizeof(chk));
    for (int i=1; i<=N; i++) {
        graph[i].clear();
    }
    int A, B;
    cin >> N;
    for (int i=0; i<N-1; i++) {
        cin >> A >> B;
        graph[A].push_back(B);
        chk[B] = true;
    }
    cin >> node1 >> node2;
    solve();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        sub();
    }
}