BOJ13306 트리(C++) 오프라인 쿼리

Mieulchi·2026년 2월 15일

목록 보기

28/33

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

태그 : 자료 구조, 트리, 오프라인 쿼리

사고 과정

일단 부모-자식 관계만 주어져

인접리스트 / 배열로 연결된 노드 관리 ? -> 인접 리스트는 삭제시간때문에 안될거고, 배열은 메모리초과 나서 안될거임.

연결리스트든, 현재 구조체를 잘 쓰든 해야할거같음. 그러면 삭제는 간단하다.

탐색이 LCA가 존재하냐/아니냐 이니까.

근데 LCA2 문제랑 다른건 중간에 간선이 업데이트 됨

업데이트하면 자식노드들 싹다 바꿔줘야하는데. 유니온 파인드로 해결 될 것 같기도 하고.

20만개에 대해 결국 잘리는 노드만 부모노드를 자기로 바꾸면 되지 않을까?

이런 고민을 하다가, 태그를 열어보니 오프라인 쿼리라는 처음보는 친구가 있었다.

이게 뭔... 하면서 오프라인 쿼리에 대해 또 검색을 해보았다..

오프라인 쿼리

검색해보니 바로 이 문제가 나오더라. 이것도 웰노운이라니.. 끝이 없구나 싶었다.

문제의 핵심은, 쿼리를 뒤에서부터 수행하는 것이였다.

뭔소린고 하니, 노드간 관계를 끊는 0번 쿼리가 N-1개 주어진단다.

즉 다 끊고나면 노드 N개가 동떨어진 그런 상황인거다.

이말은, 쿼리를 뒤에서부터 수행하면 그냥 합치는 문제가 된다는 거다.

1, 3번이 부모-자식 관계라고 해보자.

1,3을 확인한다. 1,3을 끊는다. 1-3을 확인한다.

이 쿼리의 결과는 YES - NO이다.

순서와, 끊는다.를 연결한다로 뒤집으면?

1,3을 확인한다. 1,3을 연결한다. 1-3을 확인한다.

이 쿼리의 결과는 NO-YES이다.

결국 시작이 모두 연결된 상태에서 노드를 마구 끊고 결과가 아무 연결 없는 노드들이 된다면,

굳이 처리하기 어려운 연결해제로 다루지 말고, 간단하게 합칠 수 있는 union-find로 볼 수 있게 된다.

코드

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

struct Query {
	int x;
	int a, b;
	Query() : x(0), a(0), b(0) {}
};

int n, q;

int parentNode[200001];
int parent[200001];

Query queries[400000];
vector<string> ans;

void merge(int node) {
	int p = parentNode[node];

	if (parent[p] != parent[node]) {
		parent[node] = parent[p];
	}

}

int find(int a) {
	if (parent[a] == a) {
		return a;
	}
	parent[a] = find(parent[a]);
	return parent[a];
}

void solve() {
	for (int i = 1; i <= n; ++i) {
		parent[i] = i;
	}
	for (int i = n + q - 2; i >= 0; --i) {
		Query query = queries[i];
		if (query.x == 0) {
			merge(query.a);
		}
		else {
			ans.push_back(find(query.a) == find(query.b) ? "YES" : "NO");
		}
	}
}

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

	cin >> n >> q;
	
	parentNode[1] = 1;
	for (int i = 2; i <= n; ++i) {
		cin >> parentNode[i];
	}

	int x, a, b;
	for (int query = 0; query < (n - 1) + q; ++query) {
		cin >> x;

		if (x == 0) {
			cin >> a;
			queries[query].x = x;
			queries[query].a = a;
		}
		//
		else {
			cin >> a >> b;
			queries[query].x = x;

			queries[query].a = a;
			queries[query].b = b;
		}
	}

	solve();

	for (int i = ans.size() - 1; i >= 0; --i) {
		cout << ans[i] << '\n';
	}

}