[BOJ] 3176 | 도로 네트워크

문제

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

풀이

sparse table을 이용한 LCA 문제.

LCA를 구현하고, 다음과 같은 DP 테이블을 만든다.

maxi[i][j] = i의 j번째 조상까지의 도로중 가장 긴 도로의 길이.

maxi[i][j] = max(maxi[parent[i][j - 1]][j - 1], maxi[i][j-1]);

maxi[i][j] = i의 j번째 조상까지의 도로중 가장 짧은 도로의 길이.

mini[i][j] = min(mini[parent[i][j - 1]][j - 1], mini[i][j - 1]);

이를 잘 이용하여 풀면 된다.

sparse-table 초기화에 O(NlogN)

쿼리 실행 중, 두 노드의 높이를 맞추는데 O(logN), 가장 긴/짧은 도로를 찾는데 O(logN)이므로,

쿼리 실행의 시간복잡도는 O(QlogN).

전체 시간복잡도는 O((Q+N)logN)

소스

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define P pair<int,int>
using namespace std;

int n, q, depth[110000], mini[110000][20], maxi[110000][20], parent[110000][20];

vector<P> G[110000];
queue<int> Q;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back({ b,c });
		G[b].push_back({ a,c });
	}
	depth[1] = 1;
	parent[1][0] = 1;
	Q.push(1);
	while (!Q.empty()) {
		int now = Q.front();
		Q.pop();
		for (P nxt : G[now]) {
			if (!depth[nxt.first]) {
				depth[nxt.first] = depth[now] + 1;
				mini[nxt.first][0] = nxt.second;
				maxi[nxt.first][0] = nxt.second;
				parent[nxt.first][0] = now;
				Q.push(nxt.first);
			}
		}
	}
	for (int i = 1; i < 20; i++)
		for (int j = 1; j <= n; j++) {
			parent[j][i] = parent[parent[j][i - 1]][i - 1];
			maxi[j][i] = max(maxi[parent[j][i - 1]][i - 1], maxi[j][i-1]);
			mini[j][i] = min(mini[parent[j][i - 1]][i - 1], mini[j][i - 1]);
		}
	cin >> q;
	while (q--) {
		int a, b, dismax=0, dismin=1000000;
		cin >> a >> b;
		if (depth[a] < depth[b])
			swap(a, b);
		int diff = depth[a] - depth[b];
		for(int i=0; diff; i++) {
			if (diff & 1) {
				dismax = max(dismax, maxi[a][i]);
				dismin = min(dismin, mini[a][i]);
				a = parent[a][i];
			}
			diff /= 2;
		}
		if (a != b) {
			for (int i = 19; i >= 0; i--) {
				if (parent[a][i] != parent[b][i]) {
					dismax = max({ dismax, maxi[a][i], maxi[b][i] });
					dismin = min({ dismin, mini[a][i], mini[b][i] });
					a = parent[a][i], b = parent[b][i];
				}
			}
			dismax = max({ dismax, maxi[a][0], maxi[b][0] });
			dismin = min({ dismin, mini[a][0], mini[b][0] });
		}
		cout << dismin << " " << dismax << "\n";
	}
}