[백준 11438] LCA2

문제

www.acmicpc.net/problem/11438

 

알고리즘

sparse table

 

풀이

LCA를 빠르게 처리하는 문제입니다.

 

LCA를 구하는 과정은 두 단계로 나뉩니다. 첫 번째는 두 정점 간의 깊이를 일치시키고 만일 이때 정점이 일치하지 않다면 각자의 $2^i$ 위의 정점을 살펴보며 다르다면 트리에서 올라가면 됩니다. 높이가 일치한 후 $2^i$ 위의 정점이 다르다면 올라갈 여지가 남았다는 뜻이기 때문입니다.

 

LCA쿼리당 요구하는 시간복잡도는 $O(logN)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e5;

int N, Q;

vector<int> adj[MAXN];
int table[18][MAXN], dep[MAXN];
void dfs(int here) {
    for (auto there : adj[here]) {
        if (there ^ table[0][here]) {
            table[0][there] = here;
            dep[there] = dep[here] + 1;
            dfs(there);
        }
    }
}

void init() {
    for (int i = 1; i < 18; ++i) {
        rep(j, N) {
            table[i][j] = table[i - 1][table[i - 1][j]];
        }
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v])
        swap(u, v);

    for (int i = 17; i >= 0; --i) {
        if ((dep[u] - dep[v]) & (1 << i)) {
            u = table[i][u];
        }
    }
    if (u == v)
        return u;

    for (int i = 17; i >= 0; --i) {
        if (table[i][u] ^ table[i][v]) {
            u = table[i][u];
            v = table[i][v];
        }
    }
    return table[0][v];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N - 1) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(0);
    init();

    cin >> Q;
    while (Q--) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        cout << lca(u, v) + 1 << '\n';
    }

    return 0;
}