11438 LCA2 (최소 공통 조상) [Platinum V]

 

11438번: LCA 2

 

 

11437 LCA (최소 공통 조상) [Gold III]

LCA2는 LCA와 똑같은 문제지만 보다 빠른 속도를 요구하고있습니다.

이 문제를 해결하기 위해서는 최소 공통 조상을 찾는 함수의 '두 노드의 깊이를 맞추는 부분'과 '공통 조상을 찾는 부분'를 효율적으로 풀어야합니다.

 

속도를 줄일 수 있는 부분은 두 노드의 깊이를 맞추는 부분입니다.

점화식을 통해 부모 노드를 구하면 이를 굉장히 빠르게 해결할 수 있습니다.

// 부모 노드 점화식
parent[k][n] = parent[k - 1][ parent [k - 1][ n ] ];

 

// depth 차이 만큼 한번에 depth를 맞춰줌
for (int k = kmax; k >= 0; k--)
{ 
    if (pow(2, k) <= depth[b] - depth[a]) {
        if (depth[a] <= depth[parent[k][b]])
            b = parent[k][b];
    }
}

 

#include <iostream>
#include <vector>

#include <cmath>

using namespace std;

vector<vector<int>> tree;
vector<int> depth;
vector<bool> visited;
static int parent[21][100001];
static int kmax;

void BFS(int i);
int LCA(int a, int b);
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N; 
	tree.resize(N + 1);
	depth.resize(N + 1);
	visited.resize(N + 1);

	for (int i = 0; i < N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	 }

	int temp = 1;
	kmax = 0;
	while (temp <= N) {
		temp <<= 1;
		kmax++;
	}

	BFS(1);

	for (int k = 1; k <= kmax; k++) {
		for (int n = 1; n <= N; n++) {
			parent[k][n] = parent[k - 1][parent[k - 1][n]];
		}
	}

	
	vector<int> result;
	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		result.push_back(LCA(a, b));
	}
	for (int i : result)
		cout << i << "\n";

}

int LCA(int a, int b) {
	if (depth[a] > depth[b]) {
		int temp = a;
		a = b;
		b = temp;
	}

	for (int k = kmax; k >= 0; k--)
	{
		if (pow(2, k) <= depth[b] - depth[a]) {
			if (depth[a] <= depth[parent[k][b]])
				b = parent[k][b];
		}
	}
    
	while (a != b)
	{
		a = parent[0][a];
		b = parent[0][b];
	}
	return a;
}

void BFS(int i)
{
	queue<pair<int, int>> q;
	q.push(make_pair(i, 0));

	while (q.size())
	{
		int curId = q.front().first;
		int curLevel = q.front().second;
		q.pop();

		visited[curId] = true;
		depth[curId] = curLevel;

		for (int i : tree[curId]) {
			if (visited[i])
				continue;

			parent[0][i] = curId; 


			q.push(make_pair(i, curLevel + 1));
		}
	}
}