[C/C++] 백준 - 11438번 : LCA2

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

11438번: LCA 2

LCA1도 있고 LCA2도 있는데 이 문제는 LCA2이다.

이유는 LCA1보다 시간효율성을 따져야하기 때문이다.

확인해야할 노드는 늘어났는데 시간효율성은 더 줄어들었다.

이 문제는 O(logn)으로 해결해야한다. 나도 이 알고리즘은 다른 분들의 블로그를 참고하면서 공부했다. 아직 불완전한 상태이다.

https://justicehui.github.io/medium-algorithm/2019/03/28/LCA/

[트리] 최소 공통 조상(LCA)

위 블로그에서 공부했다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 18549876543
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, M;
const int MAX = 20;
vector<int> adj[100001];
int depth[100001];
int parent[100001][MAX];

void Input() {
	cin >> N;
	for (int T = 0; T < N - 1; ++T) {
		int From, To;
		cin >> From >> To;
		adj[From].push_back(To);
		adj[To].push_back(From);
	}
}

void Init() {
	// 루트노드의 깊이는 무조건 0
	fill(depth, depth + N + 1, -1);
	memset(parent, -1, sizeof(parent));
	for (int i = 0; i < MAX - 1; i++) parent[1][i] = 1;
	depth[1] = 0;
}

void Depth_Check(int node) {
	for (int next : adj[node]) {
		if (depth[next] == -1) {
			depth[next] = depth[node] + 1;
			parent[next][0] = node;
			Depth_Check(next);
		}
	}
	return;
}

void Depth_Link() {
	for (int power = 1; power < MAX; ++power) {
		for (int node = 1; node <= N; ++node) {
			parent[node][power] = parent[parent[node][power - 1]][power - 1];
		}
	}
	return;
}

int LCA(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	int diff = depth[u] - depth[v];
	for (int i = 0; diff != 0; ++i) {
		if (diff % 2 == 1) u = parent[u][i];
		diff /= 2;
	}

	if (u != v) {
		for (int i = MAX - 1; i >= 0; --i) {
			if (parent[u][i] != -1 && parent[u][i] != parent[v][i]) {
				u = parent[u][i];
				v = parent[v][i];
			}
		}
		u = parent[u][0];
	}
	return u;
}

void Output() {
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		int node1, node2;
		cin >> node1 >> node2;
		cout << LCA(node1, node2) << endl;
	}
}

int main() {
	CUNLINK;
	Input();
	Init();
	Depth_Check(1);
	Depth_Link();
	Output();

	return 0;
}