백준 13306번 트리

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

13306번: 트리

풀이

마지막에 받은 쿼리부터 역순으로 실행하는 것이 풀이의 핵심입니다. 트리의 간선을 끊는 동작은 처리하기 어렵지만, 두 정점을 잇는 연산은 유니온 파인드를 통해 쉽게 할 수 있기 때문입니다. 따라서 트리에서 간선을 하나씩 끊는 것이 아니라 모든 정점이 연결되지 않은 상태에서 쿼리를 역순으로 보며 각 쿼리에 대해 다음과 같이 실행합니다.

 

쿼리 1 : 0 b

원래 명령과 반대로 b와 b의 부모 정점을 하나의 그룹으로 묶습니다.

 

쿼리 2 : 1 c d

c와 d가 같은 그룹에 있는지를 검사합니다. 만약 c와 d가 같은 그룹이라면 쿼리를 원래 순서대로 수행했을 때 c와 d를 잇는 간선이 아직 존재한다는 뜻이며, 다른 그룹이라면 이미 c와 d 사이의 연결이 끊겼다는 것을 의미합니다.

 

경로 압축만 적용했으니 유니온 파인드 연산의 시간복잡도는 $O(logN)$ 입니다. 각 쿼리마다 유니온 파인드 연산을 한 번씩 수행하므로 쿼리의 개수를 $M$개라고 하면 총 시간복잡도는 $O(MlogN)$입니다.

 

코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#define fast ios::sync_with_stdio(0), cin.tie(nullptr);
#define S 200005
using namespace std;
int uftree[S], par[S];
int find(int a) {
    if (uftree[a] == -1)
        return a;
    return uftree[a] = find(uftree[a]);
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b)
        uftree[a] = b;
}
int quary[S * 2][3];
stack<string> stk;
int main() {
    fast;
    int n, q, tmp;
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        cin >> tmp;
        par[i] = tmp;
        uftree[i] = -1;
    }
    par[1] = uftree[1] = -1;
    n += q - 1;
    for (int i = 1; i <= n; i++) {
        cin >> quary[i][0] >> quary[i][1];
        if (quary[i][0])
            cin >> quary[i][2];
    }
    while (n) {
        if (quary[n][0]) {
            if (find(quary[n][1]) == find(quary[n][2]))
                stk.push("YES");
            else
                stk.push("NO");
        }
        else
            merge(quary[n][1], par[quary[n][1]]);
        n--;
    }
    while (!stk.empty()) {
        string now = stk.top();
        cout << now << '\n';
        stk.pop();
    }
    return 0;
}

받은 쿼리를 역순으로 처리하기 위해 배열에 모든 쿼리를 저장했습니다. 쿼리 2의 결과 또한 역순으로 출력하기 위해 스택을 사용했습니다.

 

비슷한 문제

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

2463번: 비용

그래프의 간선을 끊는 작업을 유니온 파인드를 이용해 간선을 잇는 작업으로 대체한다는 점에서 거의 똑같은 문제라고 생각해도 괜찮습니다. 유니온 파인드에서 각 그룹의 크기를 관리하는 작업을 추가하면 비슷한 아이디어로 풀 수 있습니다. 한 달 정도 전에 동아리 수업에서 다루었던 문제인데, 덕분에 풀이의 핵심 아이디어를 쉽게 떠올릴 수 있었습니다.