[BOJ] 백준 3176번: 도로 네트워크

백준문제

3176번: 도로 네트워크

이번 포스팅은 LCA와 LCA에서의 노드간 가중치, 특성 등을 다루는 방법을 논의한다.

LCA는 공통 부모노드를 찾는 알고리즘으로 2^i 번째 부모노드만을 고려하여 ( i >= 0, 인 정수) 의 lgN 복잡도로 빠르게 수행 가능하다.

이때 두 노드를 잇는 경로에서 각 경로의 distance (cost)를 다루는 문제에서 j번째 노드부터 2^i번째 부모까지의 거리 요소를 dist[i][j]로 저장하면 역시 lgN의 복잡도로 다룰수있다. (LCA찾는 메커니즘과 동일)

만약 j번째 노드에서 2^i 번째 부모 노드까지 최대 경로 비용은 max_dist[i][j] = max(max[i-1][j], max[i-1][dp[i-1][j]]) 와 같이 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;
vector<pair<int,int> > v[100001];
int n,q;
int min_d[20][100001]={0,};
int max_d[20][100001] ={0,}; 
int depth[100001];
int dp[20][100001]={0,}; // j번째 노드의 2^i 부모 노드
// 루트는 1
void recv(int node,int parent,int len, int d){
	depth[node] = d;
	dp[0][node] = parent;
	min_d[0][node] = len;
	max_d[0][node] = len;
	for(auto nxt: v[node]){
		if(nxt.first != parent){
			recv(nxt.first, node, nxt.second, d+1);
		}
	}
}
pair<int,int> lca(int a,int b){
	int da = depth[a];
	int db = depth[b];
	if(da < db){
		swap(a,b);		
	}
	// a가 더 깊거나 깊이가 같음
	int _max = 0;
	int _min = 1e6+1;
	da = depth[a];
	db = depth[b];
	int dif = da-db;
	for(int i = 19 ; i > -1 ; i--){
		if( (1 << i) & dif){
			_max = max(_max,max_d[i][a]);
			_min = min(_min,min_d[i][a]);
			a =  dp[i][a];
		}
	}
	
	if(a != b){
		for(int i = 19 ; i > -1 ; i --){
			if( dp[i][a] != dp[i][b]){
				_max = max(_max,max_d[i][a]);
				_min = min(_min,min_d[i][a]);
				_max = max(_max,max_d[i][b]);
				_min = min(_min,min_d[i][b]);
				a = dp[i][a];
				b = dp[i][b];
			}
		}
		_max = max(_max, max_d[0][a]);
		_min = min(_min,min_d[0][a]);
		_max = max(_max,max_d[0][b]);
		_min = min(_min,min_d[0][b]);
	}
	return {_min,_max};
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for(int i = 1; i < n ;i ++){
		int a,b,c;
		cin >> a>>b>>c;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	recv(1,0,0,0);
	for(int i= 1; i < 20 ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			int p = dp[i-1][dp[i-1][j]];
			if(p){
				dp[i][j] = p;
			}
		}
	}
	for(int i = 1; i < 20 ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			int hp = dp[i-1][j];
			if(hp){
				max_d[i][j] = max(max_d[i-1][hp] , max_d[i-1][j]);
				min_d[i][j] = min(min_d[i-1][hp],min_d[i-1][j]);
			}
		}
	}
	cin >> q;
	for(;q--;){
		int a,b;
		cin >>a >> b;
		pair<int,int> p = lca(a,b);
		cout << p.first <<" " << p.second<<"\n";
	}
}