[BOJ 11438] LCA 2

문제

www.acmicpc.net/problem/11438

11438번: LCA 2

 

---

풀이

문제 제목 그대로 LCA(Lowest Common Ancestor)를 사용합니다.

각 노드의 자식 정보를 담은 배열 \(graph\)와 각 노드의 조상 정보를 담은 배열 \(par\), 그리고 각 노드의 깊이를 담은 배열 \(depth\)가 있을 때 주어진 트리를 순회하면서 다음 작업을 수행합니다.

 

현재 노드를 \(i\)라고 할 때:

 

1. \(par[i][j]\)에 \(i\)의 \(2^j\)번째 조상에 대한 정보를 저장합니다. (이때, \(j\)의 범위는 \(0\)부터 \(\log_{2}N\)까지입니다.)
2. \(graph[i]\)에 저장된 \(i\)의 자식들을 \(c_{1}, c_{2}, c_{3}, ... , c_{m}\)이라 할 때 \(depth[c_{j}]=depth[i]+1, par[c_{j}][0]=i\)가 됩니다.
3. 배열에 값을 저장한 다음 각 \(c_{j}\)를 \(i\)로 한다음 다시 작업을 실행합니다.

작업을 다 수행한 다음 \(M\)번에 걸쳐 입력받은 \(a\), \(b\)의 최소 공통 조상을 구합니다:

1. \(a\)와 \(b\)중 깊이가 더 깊은 노드를 깊이가 더 얕은 노드의 깊이와 같게 해줍니다. (이때, 깊이가 더 깊은 노드를 \(2^{log_{2}N}\)번째, \(2^{log_{2}N-1}\)번째, \(2^{log_{2}N-2}\)번째, ... , \(2^0(=1)\)번째 순서로 조상을 보면서 깊이가 같아질 때까지 조상을 타고 올라갑니다.)

2. 서로의 노드가 같아질 때까지 \(2^{log_{2}N}\)번째, \(2^{log_{2}N-1}\)번째, \(2^{log_{2}N-2}\)번째, ... , \(2^0\)번째 순서로 서로의 조상들을 타고 올라갑니다.

 

3. 서로의 조상이 같을 때의 조상이 답이 됩니다.

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int MAX_LVL = (int)floor(log2(100000));

vector<vector<int>> graph;
vector<vector<int>> par;
vector<int> depth;

void solve(int cur, int pnode) {
    depth[cur] = depth[pnode] + 1;
    par[cur][0] = pnode;

    for (int i = 1; i <= MAX_LVL; ++i) {
        int tmp = par[cur][i - 1];
        par[cur][i] = par[tmp][i - 1];
    }

    for (int i = 0; i < graph[cur].size(); ++i) {
        int next = graph[cur][i];
        if (next != pnode)
            solve(next, cur);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N;
    graph.resize(N + 1);
    par.resize(N + 1, vector<int>(MAX_LVL, 0));
    depth.resize(N + 1, 0);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    solve(1, 0);

    cin >> M;
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        if (depth[a] != depth[b]) {
            if (depth[a] > depth[b])
                swap(a, b);
            for (int i = MAX_LVL; i >= 0; --i)
                if (depth[a] <= depth[par[b][i]])
                    b = par[b][i];
        }

        int lca = a;
        if (a != b) {
            for (int i = MAX_LVL; i >= 0; --i) {
                if (par[a][i] != par[b][i]) {
                    a = par[a][i];
                    b = par[b][i];
                }
                lca = par[a][i];
            }
        }

        cout << lca << "\n";
    }

    return 0;
}