[백준] 11437 - LCA

https://www.acmicpc.net/problem/11437

11437번: LCA

 

이전 포스트를 참고하였다면 쉽게 풀 수 있는 문제이다.

n 제한이 50000이라서 높이를 최대 16(2^16 = 65536)으로 주었다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v;
int n, depth[50001], parent[50001][17];

void dfs(int pre, int node, int h) {
    depth[node] = h;
    for (auto& i : v[node]) {
        if (i != pre) {
            parent[i][0] = node;
            dfs(node, i, h + 1);
        }
    }
}

int getA(int a, int b) {
    if (depth[a] != depth[b]) {
        if (depth[a] > depth[b]) {
            swap(a, b);
        }

        for (int i = 16; i >= 0; i--) {
            if (parent[b][i] == 0) continue;
            if (depth[a] <= depth[parent[b][i]]) {
                b = parent[b][i];
            }
        }
    }

    int ret = a;

    if (a != b) {
        for (int i = 16; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
            ret = parent[a][i];
        }
    }

    return ret;
}

int main() {

    cin >> n;
    v.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs(0, 1, 1);

    for (int i = 1; i <= 16; i++) {
        for (int j = 2; j <= n; j++) {
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
        }
    }

    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cout << getA(a, b) << '\n';
    }
}