취미로 코딩하기

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

이번에 볼 문제는 백준 24835번 문제인 1-Trees and Queries이다.
문제는 아래 링크를 확인하자.

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

트리에 새 에지를 하나 추가해 얻을 수 있는 그래프를 1-Tree라고 한다. 1-Tree에는 하나의 사이클만이 존재한다는 특징이 있다.

새 1-Tree 위에서 경로의 길이의 홀짝별로 "한 에지를 3회 이상 지나지 않으면서" 두 점 a와 b 사이를 빠르게 이동하는 방법은 다음 세가지를 조사해보는 것으로 충분하다:

1. 원래의 트리에서 움직이는 경로대로 이동한다.

2. 원래의 트리 위에서 이동하듯 a에서 x로 이동한 뒤 x-y간 에지를 따라 이동하고 원래의 트리 위에서 이동하듯 y에서 b로 이동한다.

3. 원래의 트리 위에서 이동하듯 a에서 y로 이동한 뒤 y-x간 에지를 따라 이동하고 원래의 트리 위에서 이동하듯 x에서 b로 이동한다.

x와 y를 잇는 에지를 따라 이동하는 것은 거리 1, 그 외의 거리는 원래의 트리 위에서의 거리를 계산하는 것으로 모든 거리를 구할 수 있으므로, LCA를 이용하여 빠르게 거리를 구해 문제를 해결할 수 있다.

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

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

int N;
vector<int> G[100001];

int depth[100001];
int table[20][100001];

void dfs(int cur, int par) {
	table[0][cur] = par;
	depth[cur] = depth[par] + 1;
	for (auto node : G[cur]) {
		if (node == par) continue;
		dfs(node, cur);
	}
}

void tableinit() {
	dfs(1, 0);
	for (int i = 1; i < 20; i++) {
		for (int node = 1; node <= N; node++) {
			table[i][node] = table[i - 1][table[i - 1][node]];
		}
	}
}

int dist(int x, int y) {
	int ret = 0;
	if (depth[x] < depth[y]) swap(x, y);
	int depthdiff = depth[x] - depth[y];
	int digit = 0;
	ret += depthdiff;
	while (depthdiff) {
		if (depthdiff & 1) x = table[digit][x];
		depthdiff >>= 1;
		digit++;
	}

	if (x == y) return ret;

	for (int d = 19; d > -1; d--) {
		if (table[d][x] == table[d][y]) continue;
		ret += (1 << (d + 1));
		x = table[d][x], y = table[d][y];
	}

	return ret + 2;
}

void query() {
	int x, y, a, b, k; cin >> x >> y >> a >> b >> k;
	int evendist = 1000000008, odddist = 1000000007;

	int dab = dist(a, b), dax = dist(a, x), day = dist(a, y), dbx = dist(b, x), dby = dist(b, y);
	if (dab & 1) odddist = min(odddist, dab);
	else evendist = min(evendist, dab);
	if ((dax + 1 + dby) & 1) odddist = min(odddist, (dax + 1 + dby));
	else evendist = min(evendist, (dax + 1 + dby));
	if ((day + 1 + dbx) & 1) odddist = min(odddist, (day + 1 + dbx));
	else evendist = min(evendist, (day + 1 + dbx));

	if (k & 1) {
		if (k < odddist) cout << "NO\n";
		else cout << "YES\n";
	}
	else {
		if (k < evendist) cout << "NO\n";
		else cout << "YES\n";
	}
}

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);
	}

	tableinit();

	int Q; cin >> Q;
	while (Q--) {
		query();
	}
}