[백준 11437] LCA (C++)

문제 링크: https://www.acmicpc.net/problem/11437

11437번: LCA

1. 주의할 점

- Tree와 depth를 잘 설정해야한다.

- LCA 알고리즘을 정확히 이해해야한다.

 

2. 구현

- 첫 번째 시도: LCA에 대한 개념을 모르고 Parent,Depth 배열만을 이용해서 구현 -> TLE

- 두 번째 시도: LCA에 대한 개념을 익히고 적용 -> lg|Node의 최대갯수|의 올림 만큼만 Tree를 밑으로 판다고 생각한다.

  Depth가 다른경우 우선 Depth부터 맞추고, 만약 2개의 현재 값이 같다면 그 값을 Return

  현재 값이 다를 경우, 현재의 parent로 값을 올려서 비교한다(현재의 Depth -1만큼. 굳이 lg|Node의 최대갯수|의 올림만큼 할 필요가 없다.) 

 

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
vector<int> v[50001];
int tree[17][50001], depth[50001];
int num;

int find_LCA(int child, int parent) {
	int diff = depth[child] - depth[parent];
	for (int i = 16; i >= 0; i--) {
		int tt = pow(2, i);
		if (tt <= diff) {
			child = tree[i][child];
			diff -= tt;
		}
	}
	if (child == parent) return child;
	int tt = depth[child] - 1;
	while (tt > 0) {
		if (tree[0][child] == tree[0][parent])
			break;
		child = tree[0][child];
		parent = tree[0][parent];
		tt--;
	}
	return tree[0][child];
}

void make_tree() {
	queue<int> q;
	q.push(1);
	tree[0][1] = 1;
	depth[1] = 1;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (depth[next] == 0) {
				tree[0][next] = cidx;
				depth[next] = depth[cidx] + 1;
				q.push(next);
			}
		}
	}
}

void find_parent() {
	for (int i = 1; i < 17; i++) {
		for (int j = 1; j <= num; j++)
			tree[i][j] = tree[i - 1][tree[i - 1][j]];
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int a, b, query;
	cin >> num;
	for (int i = 0; i < num-1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	make_tree();
	find_parent();
	cin >> query;
	int result;
	for (int i = 0; i < query; i++) {
		cin >> a >> b;
		result = depth[a] > depth[b] ? find_LCA(a, b) : find_LCA(b, a);
		cout << result << '\n';
	}
	system("pause");
	return 0;
}