취미로 코딩하기

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

이번에 볼 문제는 백준 15480번 문제인 LCA와 쿼리이다.
문제는 아래 링크를 확인하자.

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

임의의 노드를 루트로 잡은 rooted tree에서, 어떤 노드를 루트로 잡았을 때의 임의의 두 노드 사이의 LCA를 찾아내는 문제이다.

힌트 - 트리 위에서 임의로 세 점을 잡아서, 두 점끼리의 LCA를 각각 구했을 때 어떠한 특징이 있는지 관찰해보자. 이를 통해 문제를 해결할 수 있다.

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

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

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

int T[100001][17];

void Tinit(int N) {
	for (int k = 1; k < 17; k++) {
		for (int i = 1; i <= N; i++) {
			T[i][k] = T[T[i][k - 1]][k - 1];
		}
	}
}

void dfs(int current, int parent, int lv) {
	level[current] = lv++;
	for (auto node : G[current]) {
		if (node == parent) T[current][0] = parent;
		else dfs(node, current, lv);
	}
}

int lca(int x, int y) {
	if (level[x] != level[y]) {
		if (level[x] < level[y]) swap(x, y);
		int diff = level[x] - level[y];
		int temp = 0;
		while (diff > 0) {
			if (diff & 1) x = T[x][temp];
			diff >>= 1;
			temp++;
		}
	}

	if (x != y) {
		for (int k = 16; k >= 0; k--) {
			if (T[x][k] == T[y][k]) continue;
			x = T[x][k], y = T[y][k];
		}
		x = T[x][0], y = T[y][0];
	}

	return x;
}

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

	int N; cin >> N;
	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	T[1][0] = 1;
	dfs(1, 1, 0);
	Tinit(N);

	int Q; cin >> Q;
	while (Q--) {
		int r, x, y; cin >> r >> x >> y;
		int rx = lca(r, x), ry = lca(r, y), xy = lca(x, y);
		if (rx == ry) cout << xy << '\n';
		else if (xy == rx) cout << ry << '\n';
		else cout << rx << '\n'; // xy == ry
	}
}