[백준] 11438 LCA2

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

 

최소공통조상 문제입니다.

두 노드의 공통 조상을 구할때의 과정은 다음과 같습니다.

1. 두 노드의 높이를 맞춰줍니다.

2. 한 단계씩 높이를 동시에 높히면서 공통조상이 나올때까지 반복합니다.

 

두 과정에서 한칸씩 움직여 선형으로 탐색을 할 수 있지만,

log형태로 탐색할 수 있습니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { 0,-1,0,1 }, dx[] = { -1,0,1,0 };
int a, b, N,M, p[100001][20], d[100001], v[100001];
vi adj[100001];
void dfs(int cur, int depth) {
	REP(i, (int)log2(depth)) {
		p[cur][i] = p[p[cur][i - 1]][i - 1];
	}
	for (auto r : adj[cur]) {
		if (!p[r][0]) {
			p[r][0] = cur;
			d[r] = depth+1;
			dfs(r, depth + 1);
		}
	}
}
int sameD(int temp, int cur) {
	while (temp > 0) {
		int k = (int)log2(temp);
		temp -= pow(2, k);
		cur = p[cur][k];
	}
	return cur;
}
int query(int a, int b) {
	while (1) {
		int f = 1;
		int M = (int)log2(d[a]);
		for (int i = M; i >= 0; i--) {
			if (p[a][i] != p[b][i]) {
				a = p[a][i];
				b = p[b][i];
				f = 0;
				break;
			}
		}
		if (f) {
			return p[a][0];
		}
	}
}
int main() {
	FAST;
	cin >> N;
	rep(i, N - 1) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	p[1][0] = -1;
	dfs(1, 0);
	cin >> M;
	while (M--) {
		cin >> a >> b;
		if (d[a] != d[b]) {
			int temp = abs(d[a] - d[b]);
			d[a] > d[b] ? a = sameD(temp, a) : b = sameD(temp, b);
		}
		if (a == b) {
			cout << a << "\n";
			continue;
		}
		cout << query(a, b) << "\n";
	}
}

최소공통조상 문제입니다.