취미로 코딩하기

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

이번에 볼 문제는 백준 15564번 문제인 Äventyr 2이다.
문제는 아래 링크를 확인하자.

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

먼저 주어지는 트리를 센트로이드분해를 해두자.

각 노드에 대하여 그 노드가 센트로이드가 되는 "센트로이드분해 상의 서브트리" 위에서의 답을 미리 전처리해두고, 각 쿼리가 들어올 때마다 해당 노드를 포함하는 각 "센트로이드분해 상의 서브트리"에 대하여 해당 노드에서의 최단거리(없다면 INF)를 구해보자. 센트로이드 분해를 제대로 이해했다면 위에서 구한 값중 최솟값이 답이 된다는 것은 쉽게 관찰할 수 있다.

트리 위에서의 두 노드 사이의 거리는 별도의 sparse table을 만들어 LCA를 찾는 방식으로 계산할 수 있다.

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

#define MAX 1000000007
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, Q;
vector<int> G[100001];
int table[100001][17];
int level[100001];
void dfs(int cur, int par, int lv) {
	level[cur] = lv;
	for (auto& node : G[cur]) {
		if (node == par) continue;
		dfs(node, cur, lv + 1);
	}
}
void tableinit() {
	for (int k = 1; k < 17; k++) {
		for (int i = 1; i <= N; i++) {
			table[i][k] = table[table[i][k - 1]][k - 1];
		}
	}
}
int dist(int u, int v) {
	int ret = 0;
	if (level[u] < level[v]) swap(u, v);
	int tmp = level[u] - level[v];
	int idx = 0;
	while (tmp) {
		if (tmp & 1) {
			ret += (1 << idx);
			u = table[u][idx];
		}
		tmp >>= 1;
		idx++;
	}
	if (u == v) return ret;
	for (int k = 16; k > -1; k--) {
		if (table[u][k] == table[v][k]) continue;
		ret += (1 << k);
		ret += (1 << k);
		u = table[u][k], v = table[v][k];
	}
	return ret + 2;
}

bool visited[100001];
int childcnt[100001];
int centroidparent[100001];
int dfs2(int cur, int par) {
	int ret = 1;
	for (auto& node : G[cur]) {
		if (node == par || visited[node]) continue;
		ret += dfs2(node, cur);
	}
	return childcnt[cur] = ret;
}
int centroid(int cur, int par, int K) {
	for (auto& node : G[cur]) {
		if (node == par || visited[node]) continue;
		if (childcnt[node] > K) return centroid(node, cur, K);
	}
	return cur;
}
void centroid_decomposition(int cur, int par) {
	dfs2(cur, 0);
	cur = centroid(cur, -1, childcnt[cur] / 2);
	centroidparent[cur] = par;

	visited[cur] = 1;
	for (auto& node : G[cur]) {
		if (visited[node]) continue;
		centroid_decomposition(node, cur);
	}
}

int dp[100001];
void upd(int old) {
	int cur = old;
	while (cur) {
		dp[cur] = min(dp[cur], dist(cur, old));
		int par = centroidparent[cur];
		cur = par;
	}
}

void qry(int old) {
	int ret = MAX;
	int cur = old;
	while (cur) {
		ret = min(ret, dp[cur] + dist(old, cur));
		int par = centroidparent[cur];
		cur = par;
	}

	if (ret == MAX) cout << -1 << '\n';
	else cout << ret << '\n';
}

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

	cin >> N >> Q;
	for (int u = 2; u <= N; u++) {
		int v; cin >> v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		table[u][0] = v;
	}
	tableinit();
	dfs(1, 0, 1);

	centroid_decomposition(1, 0);

	for (int i = 1; i <= N; i++) dp[i] = MAX;

	while (Q--) {
		int q, x; cin >> q >> x;
		if (q == 1) upd(x);
		else qry(x);
	}
}