백준 11438번 : LCA 2 (c++)

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

11438번: LCA 2

문제

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

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

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

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

예제 입력 1 
15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15
예제 출력 1 
2
4
2
1
3
1

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAX = 100001;
int N,M;
vector <int> node[MAX];
int parent[21][MAX];
int depth[MAX];
queue <int> q;
int maxK;

void dfs(int p, int f) {
	for (int i = 0; i < node[p].size(); i++)
	{
		int c = node[p][i];
		if (f == c)	continue;
		depth[c] = depth[p] + 1;
		parent[0][c] = p;
		for (int j = 1; j < 21; j++)
		{
			parent[j][c] = parent[j - 1][parent[j - 1][c]];;
		}
		dfs(c, p);
	}
}

void makeGraph() {
	int E = N - 1;
	while (E--) {
		int u, v;
		cin >> u >> v;
		node[u].push_back(v);
		node[v].push_back(u);
	}
	dfs(1,0);
}

int lca(int a, int b) {
	if (depth[a] > depth[b]) {
		swap(a, b);
	}
	for (int i = 20; i >= 0; i--)
	{
		if ((1 << i) <= depth[b] - depth[a]) {
			b = parent[i][b];
		}
	}
	if (a == b)	return a;
	for (int i = 20; i >=0 ; i--)
	{
		if (parent[i][a] != parent[i][b]) {
			a = parent[i][a];
			b = parent[i][b];
		}
	}
	return parent[0][a];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	
	cin >> N;
	makeGraph();
	cin >> M;
	while (M--) {
		int a, b;
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}

	return 0;
}