BOJ-11438-LCA2

[changicho]

11438. LCA2

링크

난이도	정답률(_%)
Platinum V	33

설계

최소 공통 조상

주의! 최소 공통 조상을 비교할 때는 2^k만큼 떨어진 조상 중 에서 k가 제일 클 때부터 비교한다.

정리

내 코드	빠른 코드
132

고생한 점

code

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> graph[100001];
int visited[100001];
int depths[100001];
// it means the parent of current index;
int links[100001][31];

void dfs(int current, int depth) {
	visited[current] = true;
	depths[current] = depth;

	for (int next : graph[current]) {
		if (visited[next])	continue;

		links[next][0] = current;
		dfs(next, depth + 1);
	}
}

int LowestCommonAncestor(int first, int second) {
	if (depths[first] > depths[second]) swap(first, second);

	// make second's depth same with first's depth
	for (int i = 30; i >= 0; i--) {
		// 1 << i means pow(2,i);
		if (depths[second] - depths[first] >= (1 << i)) {
			second = links[second][i];
		}
	}

	if (first == second) return first;

	for (int p = 30; p >= 0; p--) {
		if (links[first][p] != links[second][p]) {
			first = links[first][p];
			second = links[second][p];
		}
	}
	return links[first][0];
}

void solution() {
	int N, M;
	int max_V = 0;

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		int parent, child;
		cin >> parent >> child;

		graph[parent].push_back(child);
		graph[child].push_back(parent);
	}

	dfs(1, 0);

	for (int j = 1; j < 30; j++) {
		for (int i = 1; i <= N; i++) {
			links[i][j] = links[links[i][j - 1]][j - 1];
		}
	}

	cin >> M;

	while (M--) {
		int first, second;
		cin >> first >> second;

		int lca = LowestCommonAncestor(first, second);
		cout << lca << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}