BOJ 11438 LCA 2

1 개요

BOJ 11438 LCA 2

• 백준 온라인 저지 11438번 문제
• BOJ 43단계

2 같이 보기

• BOJ 11437 LCA
• BOJ 11438 LCA 2

3 C++

#include <bits/stdc++.h>
using namespace std;

int N, M;
int depth[100001];
int A[100001][18];
vector <int> adj[100001];
bool visited[100001];

void dfs(int parent, int cur, int paramDepth) {
	if (visited[cur]) return;
	visited[cur] = true;
	depth[cur] = paramDepth;
	A[cur][0] = parent;
	for (int i=0; i<adj[cur].size(); i++) {
		dfs(cur, adj[cur][i], paramDepth+1);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) {
	    swap(a, b);
	}
	if (depth[a] != depth[b]) {
		int d = depth[a] - depth[b];
		for (int i = 0; i <= 17; i++) {
			if (d & (1 << i)) {
				a = A[a][i];
			}
		}
	}
	if (a == b) return a;
	for (int i = 17; i >= 0; i--) {
		if (A[a][i] != A[b][i]) {
			a = A[a][i];
			b = A[b][i];
		}
	}
	return A[a][0];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	int a, b;
	for (int i=0; i<N-1; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1, 1, 1);
	for (int i=1; i<=17; i++) {
		for (int j=1; j<=N; j++) {
			A[j][i] = A[A[j][i-1]][i-1];
		}
	}
	cin >> M;
	for (int i=0; i<M; i++) {
		int a, b;
		cin >> a >> b;
		cout << lca(a, b) << '\n';
	}
}