[PS] 도로 네트워크 / C++ (백준 3176번)

도로 네트워크 (백준 3176번)

 

LCA 2(백준 11438번)처럼 희소 배열을 이용한 최소 공통 조상(Binary Lifting) 알고리즘을 활용한 문제.

[PS] LCA 2 / C++ (백준 11438번)

구현이 꽤 복잡하지만 설계를 잘 하고, LCA를 적절하게 구현하면 쉽게 풀 수 있다. 

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<pair<int, int>> vec[100001];
int depth[100001], vi[100001];
pair<int, pair<int, int>> parent[100001][21];

void dfs(int node, int _depth) {
	vi[node] = 1;
	depth[node] = _depth;
	int size = vec[node].size();
	for (int i = 0; i < size; i++) {
		int next_node = vec[node][i].first, cost = vec[node][i].second;
		if (vi[next_node] == 0) {
			parent[next_node][0].first = node;
			parent[next_node][0].second.second=parent[next_node][0].second.first = cost;
			dfs(next_node, _depth + 1);
		}
	}
	return;
}

pair<int, int> LCA(int a, int b) 
{
	pair<int, int> pa = make_pair(1e9, 0);
	if (depth[a] < depth[b])swap(a, b);
	for (int i = 18; i >= 0; i--) {
		if (depth[a] - depth[b] >= (1 << i)) {
			pa.first = min(pa.first, parent[a][i].second.first);
			pa.second = max(pa.second, parent[a][i].second.second);
			a = parent[a][i].first;
		}
	}

	if (a == b)return pa;

	for (int i = 18; i >= 0; i--) {
		if (parent[a][i].first != parent[b][i].first) {
			pa.first = min(pa.first, min(parent[a][i].second.first, parent[b][i].second.first));
			pa.second = max(pa.second, max(parent[a][i].second.second, parent[b][i].second.second));
			a = parent[a][i].first;
			b = parent[b][i].first;
		}
	}

	pa.first = min(pa.first, min(parent[a][0].second.first, parent[b][0].second.first));
	pa.second = max(pa.second, max(parent[a][0].second.second, parent[b][0].second.second));
	return pa;
}

int main()
{
	int n, m;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		vec[a].push_back(make_pair(b, c));
		vec[b].push_back(make_pair(a, c));
	}
	dfs(1, 0);

	for (int i = 1; i <= 18; i++) {
		for (int j = 1; j <= n; j++) {
			pair<int, int> pa_1 = parent[j][i - 1].second;
			pair<int, pair<int, int>>pa_2 = parent[parent[j][i - 1].first][i - 1];
			pa_1.first = min(pa_1.first, pa_2.second.first);
			pa_1.second = max(pa_1.second, pa_2.second.second);
			parent[j][i] = make_pair(pa_2.first, pa_1);
		}
	}

	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		pair<int, int> pa = LCA(a, b);
		printf("%d %d\n", pa.first, pa.second);
	}
	return 0;
}