[BOJ 11438 | C++] LCA 2 :: LCA

• 문제 링크 : https://www.acmicpc.net/problem/11438
• 문제 태그 : 자료 구조, 트리. 최소 공통 조상, 희소 배열
• 참고 문제 : 2025.02.20 - [BOJ] - [BOJ 11437 | C++] LCA :: LCA

[BOJ 11437 | C++] LCA :: LCA

 

풀이

LCA 문제의 풀이에서 lca 함수만 수정하였습니다. 

 

• u와 v의 높이를 맞추는 데 Binary Lifting을 사용합니다.
• u와 v의 높이가 같은 상태에서 최소 공통 조상을 찾을 때도 Binary Lifting을 활용합니다.

예를 들어, 높이가 같은 u와 v가 있다고 가정하면, 두 정점을 최소 공통 조상의 바로 직전 노드까지 올린 후 그 부모를 출력하여 최소 공통 조상을 구합니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

vector<int>parent;
vector<int>depth;
vector<vector<int>>g;
vector<int>seen;

void dfs(int r) {
    if (seen[r]) return;
    seen[r] = true;

    for (auto x : g[r]) {
        if (seen[x]) continue;
        parent[x] = r;
        depth[x] = depth[r] + 1;
        dfs(x);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    parent.resize(n + 1, 0);
    depth.resize(n + 1, 0);
    g.resize(n + 1);
    seen.resize(n + 1, false);
    
    for (int i = 0;i < n - 1;i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int m; cin >> m;
    
    dfs(1);
    int maxDepth = 0;
    for (auto x : depth) maxDepth = max(x, maxDepth);

    int tmp = 1; int k = 0;
    while (tmp < maxDepth) tmp *= 2, k++;
    
    vector table(k + 1, vector<int>(n + 1, 0));
    for (int i = 0;i <= n;i++) table[0][i] = parent[i];
    for (int i = 1;i <= k;i++) {
        for (int j = 1;j <= n;j++) {
            table[i][j] = table[i - 1][table[i - 1][j]];
        }
    }

    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);

        int diff = depth[u] - depth[v];
        for (int i = 0;i <= k;i++) {
            if (diff >> i & 1) {
                u = table[i][u];
            }
        }

        if (u == v) return u;
        for (int i = k;i >= 0;i--) {
            if (table[i][u] == table[i][v]) continue;
            u = table[i][u];
            v = table[i][v];
        }
        return parent[u];
    };

    for (int i = 0;i < m;i++) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}

---

또 지난이야... 네? 뭐가 지났는데요? 아니, 또 진한님이라고

도움을 주신 jinhan814님 감사합니다👍