BOJ 15480 - LCA와 쿼리

boj-15480.cpp

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

#define MAX_N 100001
#define MAX_DEP 18

int N;
vector<int> adj[MAX_N];
int depth[MAX_N];
int parent[MAX_N][MAX_DEP]; // N번째 노드의 2^K번째 부모 노드

void makeTree(int cur) {
    for (int i = 0; i < adj[cur].size(); ++i) {
        int& next = adj[cur][i];
        if (depth[next] == -1) {
            depth[next] = depth[cur] + 1;
            parent[next][0] = cur;
            makeTree(next);
        }
    }
}

int LCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    int diff = depth[u] - depth[v];
    for (int i = 0; diff; ++i) {
        if (diff % 2) u = parent[u][i];
        diff /= 2;
    }

    // 높이는 같으나 LCA는 아직 다름
    if (u != v) {
        // 이것도 바텀업처럼 위에서부터 찾으면서 내려옴
        for (int d = MAX_DEP - 1; d >= 0; --d) {
            if (parent[u][d] != -1 && parent[u][d] != parent[v][d]) {
                u = parent[u][d];
                v = parent[v][d];
            }
        }
        // 마지막엔 두 부모가 같으므로 한번 더 올림
        u = parent[u][0];
    }

    return u;
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i < N; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    memset(depth, -1, sizeof(depth));
    memset(parent, -1, sizeof(parent));
    int root = 0;
    depth[root] = 0;
    makeTree(root);

    for (int k = 0; k + 1 < MAX_DEP; ++k) {
        for (int i = 1; i < N; ++i) {
            if (parent[i][k] != -1) {
                parent[i][k + 1] = parent[parent[i][k]][k];
            }
        }
    }

    int m;
    scanf("%d", &m);
    while (m--) {
        int r, u, v;
        scanf("%d %d %d", &r, &u, &v);
        --r, --u, --v;
        int u1 = LCA(r, u);
        int u2 = LCA(r, v);
        int u3 = LCA(v, u);
        int ans = u1;
        if (depth[ans] < depth[u2]) ans = u2;
        if (depth[ans] < depth[u3]) ans = u3;
        printf("%d\n", ans + 1);
    }

    return 0;
}