백준 3584번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 4

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기 LCA편이다. 사실 앞에 정리한 두 문제 11437, 11438번 문제보다도 더 쉬운 문제이다. 단순 난이도로 따지면 3584 < 11437 < 11438번 문제이다. 문제 티어만 봐도 알 수 있지 않은가? 3584는 최대 노드 개수가 1만개, 11437번은 최대 5만개에 쿼리 최대 1만개, 11438번은 최대 10만개에 쿼리도 최대 10만개에 달한다. 해당 문제는 O(n) LCA로 가볍게 풀리는 문제이지만, 사실 이 문제를 풀때엔 이미 플래티넘 5티어인 11438번을 푼 상태였기에 그냥 O(log(n)) LCA를 사용했다.

 

 문제 조건에 해당 트리는 루트가 있는 트리라고 했기 때문에, 맨 처음 트리를 초기화할 때, 부모가 있는 노드들을 제외한 하나의 노드만이 루트일 것이다. 해당 노드에서부터 트리를 초기화하면 된다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
#define MAX_A 15

int n,m;
vector<vector<int>> tree, graph;
vector<int> depths;
int target, goal;

void make_tree(int st, int h) {
    depths[st] = h;
    for(int g : graph[st]) make_tree(g, h+1);
}

void make_ancestor() {
    for (int ancestor = 1; ancestor <= MAX_A; ancestor++) {
        for (int node = 1; node <= n; node++) {
            tree[node][ancestor] = tree[tree[node][ancestor - 1]][ancestor - 1];
        }
    }
}

void input(){
    bool root[10001] = {false};
    int a, b;
    cin >> n;
    graph = vector<vector<int>>(n + 1);
    tree = vector<vector<int>>(n + 1, vector<int>(MAX_A + 1));
    depths = vector<int>(n + 1, -1);
    for (int i = 1; i < n; i++){
        cin >> a >> b;
        tree[b][0] = a;
        graph[a].push_back(b);
        root[b] = true;
    }
    cin >> target >> goal;
    for(int i = 1; i <= n; i++) {
        if(!root[i]) {
            make_tree(i, 1);
            break;
        }
    }
    make_ancestor();
}

void sol() {
    // target노드를 goal노드의 높이로 끌어올린다.
    if (depths[target] < depths[goal]){
        swap(target, goal);
    }
    int dh = depths[target] - depths[goal];
    for (int i = MAX_A; i >= 0 && dh; i--) {
        if (dh >= (1 << i)) {
            target = tree[target][i];
            dh -= (1 << i);
        }
    }

    if (target == goal){
        cout << goal << endl;
    }
    else {
        for (int i = MAX_A; i >= 0; i--) {
            if (tree[target][i] != 0 &&
                tree[target][i] != tree[goal][i]) {
                target = tree[target][i];
                goal = tree[goal][i];
            }
        }
        cout << tree[goal][0] << endl;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc;
    cin >> tc;
    while(tc--) {
        input();
        sol();
    }
}