취미로 코딩하기

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

이번에 볼 문제는 백준 28851번 문제인 Протокол <<Судного дня>>이다.
문제는 아래 링크를 확인하자.

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

$s_i$와 $k_i$로 이루어진 쿼리는 лондонского метро는 1번 역에서 멀어지는 방향으로 무제한으로 사용 가능하고 секретными тоннелями Кингсман는 (1번 역과 가까워지는 방향으로) 총 $k$번 이용 가능할 때 $s_i$로부터 이동할 수 있는 1번 역과의 가장 가까운 거리를 구하는 문제이다.

주어진 조건에 따라 1을 루트로 갖고 лондонского метро들을 에지로 갖는 트리의 $s$번 역에서 секретными тоннелями Кингсман를 이용해 1과 거리가 $x$(단, 1번 역과의 거리는 $s$번 역과의 거리보다 짧거나 같아야 한다.)인 역으로 이동할 경우 그 역이 특정(구체적으로, 1과 $s$를 잇는 (최단)경로 위의 역)됨을 확인하자. 따라서, 각 노드별로 1을 루트로 갖고 лондонского метро들을 에지로 갖는 트리 기준의 서브트리에서 이동할 수 있는 가장 1번 역과 가까운 역은 유일하게 결정된다. 모든 역에 대한 이러한 역은 DP를 이용해 $O(N+M)$에 전부 구할 수 있다.

위와 같은 이동을 $k$번 할 때 도착할 수 있는 1번 역과의 가장 가까운 거리 쿼리는 위의 정보를 이용한 sparse table을 미리 만들어 두면 각각 빠르게 처리할 수 있다.

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

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

int N, M;
vector<int> G[200001];
vector<int> GG[200001];

int lv[200001];
int table[18][200001];

void tableinit() {
	for (int k = 1; k < 18; k++) {
		for (int i = 1; i <= N; i++) {
			table[k][i] = table[k - 1][table[k - 1][i]];
		}
	}
}

int dfs(int cur) {
	int ret = cur;
	for (auto &nxt : G[cur]) {
		if (lv[nxt]) continue;
		lv[nxt] = lv[cur] + 1;
		int tmp = dfs(nxt);
		if (lv[tmp] < lv[ret]) ret = tmp;
	}
	for (auto &prv : GG[cur]) {
		if (lv[prv] < lv[ret]) ret = prv;
	}
	table[0][cur] = ret;
	return ret;
}

int Q;

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

	cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	cin >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		GG[x].emplace_back(y);
	}

	lv[1] = 1;
	dfs(1);
	tableinit();
	cin >> Q;
	while (Q--) {
		int x, K; cin >> x >> K;
		for (int k = 0; k < 18; k++) {
			if (K & 1) x = table[k][x];
			K >>= 1;
		}
		cout << x << '\n';
	}
}