[트리(LCA)] 백준 11437 LCA C++

 

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

11437번: LCA

 

#include <iostream>
#include <vector>
#define size 50001

using namespace std;

vector<int> graph[size];

int level[size];
int dp[size][30]; // log2(50001)
int visited[size];
int n;

void dfs(int v, int depth) {
	visited[v] = 1;
	level[v] = depth;

	for (auto i : graph[v]) {
		if (!visited[i]) {
			dp[i][0] = v; // dp[자식 노드][0] = 부모 노드
			dfs(i, depth + 1);
		}
	}
}

void initTable() { // i의 2^j번째 조상 = (i의 2^(j-1)번째 조상)의 2^(j-1)번째 조상
	for (int j = 1; j < 30; j++) {
		for (int i = 1; i <= n; i++) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1]; // dp[i][j] := i의 2^j번째 조상
		}
	}
}

int lca(int u, int v) {
	if (level[u] < level[v]) swap(u, v);
	int diff = level[u] - level[v];
	int i = 0;
	while(diff) { // 레벨 차이
		if (diff & 1) u = dp[u][i];
		diff >>= 1;
		i++;
	}
	if (u == v) return u; // 같은 레벨

	for (int i = 29; i >= 0; i--) { // 조상이 다르면 노드들을 조상 노드로 변경하여 다시 찾음
		if (dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
	}

	return dp[u][0]; // u!=v (u와 v의 부모 노드 같음)
}

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

	int m, a, b;

	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	dfs(1, 0);
	initTable();

	cin >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
}