최소 공통 조상(LCA)

설명

최소 공통 조상(Least Common Ancestor)는 트리에서 두 노드와 가장 가까운 공통 조상을 뜻한다. 위의 8번과 9번 노드의 LCA는 4번 노드다.

구하는 법

LCA를 구하는 법은 다음과 같다.

1. 두 노드의 depth를 계산 후, depth가 같을 때까지 큰 depth의 노드의 부모를 타고 올라간다.
2. depth가 같아지면, 두 노드가 같을 때까지 각자 부모를 타고 올라간다.
3. 두 노드가 같아지면 LCA다.

부모 노드를 한 계단씩 타고 올라가며 검사를 하니 시간복잡도는 $O(N)$이 된다. 이를 희소 테이블을 사용해 단축할 수 있다.

희소 테이블

희소 테이블에서 구간의 길이를 2의 제곱수 크기의 구간으로 나누어 쿼리를 처리한 것처럼, 부모를 타고 올라갈 때도 희소 테이블에 따라 2의 제곱수의 크기만큼 타고 올라가면 시간복잡도를 $O(\log N)$으로 줄일 수 있다.

parent[k][i] = i번 노드의 $2^{k}$번째 부모
= parent[k - 1][parent[k - 1][i]]

depth와 parent[0][i]는 root부터 DFS를 돌며 구할 수 있다.

int lca(vector<vector<int>> &parent, vector<int> &depth, int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);  //u를 더 깊은 노드로 맞춤
    }
    int l = depth[u] - depth[v];
    for (int i = parent.size() - 1; i >= 0; i--) {
        if (l & (1 << i)) {
            u = parent[i][u]; //2의 제곱수만큼 부모 건너뛰기
        }
    }
    if (u == v) {
        return u;  //같으면 그대로 반환
    }
    for (int i = parent.size() - 1; i >= 0; i--) {  //2^max 번째 부모부터 비교해 부모가 달라지면 u와 v 부모로 건너뛰기
        if (parent[i][u] != parent[i][v]) {
            u = parent[i][u];
            v = parent[i][v];
        }
    }
    return parent[0][u];  //u와 v의 부모가 같은 상태이니 u의 1번째 부모 반환하여 공통 조상 구하기
}

위와 같은 방법으로 백준 #11438 LCA 2를 해결 가능하다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void dfs(vector<vector<int>> &tree, vector<int> &depth, vector<vector<int>> &parent, int here, int dth) {
    depth[here] = dth;
    for (auto &next : tree[here]) {
        if (!depth[next]) {
            parent[0][next] = here;
            dfs(tree, depth, parent, next, dth + 1);
        }
    }
}

int lca(vector<vector<int>> &parent, vector<int> &depth, int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    int l = depth[u] - depth[v];
    for (int i = parent.size() - 1; i >= 0; i--) {
        if (l & (1 << i)) {
            u = parent[i][u];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = parent.size() - 1; i >= 0; i--) {
        if (parent[i][u] != parent[i][v]) {
            u = parent[i][u];
            v = parent[i][v];
        }
    }
    return parent[0][u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N;
    int logMax = log2(N) + 1;
    vector<vector<int>> tree(N + 1, vector<int>());
    vector<vector<int>> parent(logMax + 1, vector<int>(N + 1, 0));
    vector<int> depth(N + 1, 0);
    for (int i = 0; i < N - 1; i++) {
        int from, to;
        cin >> from >> to;
        tree[from].push_back(to);
        tree[to].push_back(from);
    }
    dfs(tree, depth, parent, 1, 1);
    for (int k = 1; k <= logMax; k++) {
        for (int i = 1; i <= N; i++) {
            if (1 <= parent[k - 1][i] && parent[k - 1][i] <= N) {
                parent[k][i] = parent[k - 1][parent[k - 1][i]];
            }
        }
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca(parent, depth, u, v) << '\n';
    }
    return 0;
}