취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 30050번 문제인 트리와 쿼리 \(10^9\)이다.
문제는 아래 링크를 확인하자.

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

1번 연산이 있어도 없어도 (루트 노드를 제외한) 모든 노드의 깊이는 초기상태보다 깊어지지 않음을 관찰하자. 한편 입력으로 주어지는 수는 \(10^9\) 이하이므로 많아야 30회 부모 노드 방향으로 이동하면 루트에 도달함을 관찰하면, 주어지는 두 점 사이에는 노드가 많아야 60개정도밖에 없다는 것을 알아낼 수 있다. 한편 쿼리가 10만개밖에 없음을 같이 생각하면, 두 점 사이의 경로에 포함되는 모든 노드를 선형적으로 방문해도 문제를 충분히 해결할 수 있음을  수 있다.

1번 연산으로 주어지는 각 노드의 새로운 루트를 map 등의 자료구조로 관리해 LCA를 찾아 문제를 해결하자. 1번 연산이 주어진 적이 없다면 그 노드의 부모는 노드번호를 2로 나눈 몫으로 구할 수 있다.

부모노드로 거슬러올라가는 과정에서 노드번호가 항상 감소한다는 점을 이용하면, 두 노드의 번호가 같아질 때까지 번호가 더 큰 노드를 부모 방향으로 거슬러올라가게 하는 것을 반복하는 것으로 두 노드 사이를 잇는 경로를 찾아낼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;

int Q;
map<int, int> mp;

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

	cin >> Q;
	while (Q--) {
		int q, x, y; cin >> q >> x >> y;
		if (q == 1) {
			if (mp.count(y)) mp[y] = x;
			else mp.insert(make_pair(y, x));
		}
		else {
			ll ans = x + y;
			while (x != y) {
				if (x > y) {
					if (mp.count(x)) x = mp[x];
					else x /= 2;
					ans += x;
				}
				else {
					if (mp.count(y)) y = mp[y];
					else y /= 2;
					ans += y;
				}
			}
			cout << ans - x << '\n';
		}
	}
}