icpc.me 3176 - CyberFlower Algorithm

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

LCA를 구하는 과정과 매우 유사하기 때문에, LCA를 모르시는 분이라면 LCA 를 보고 오시는 것을 추천드립니다.

LCA를 구하는 과정에서 부모 노드를 저장하는 table처럼 최소 거리와 최대 거리를 저장하는 parse table도 각각 하나씩 만들어 줍니다.

최소 거리를 저장하는 점화식은 min_dst[i][j]=min(min_dst[i-1][j],min_dst[i-1][par[i-1][j]])입니다. (최대 거리는 동일하니 굳이 한 번 더 하진 않겠습니다.)

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int SZ=100005;
const int MXH=18;
typedef pair<int,int> pii;
vector<pii> graph[SZ];
int par[MXH][SZ];
int min_dst[MXH][SZ];
int max_dst[MXH][SZ];
int level[SZ];
int n;
int dfs(int x, int p, int w, int lv){
	min_dst[0][x]=w;
	max_dst[0][x]=w;
	par[0][x]=p;
	level[x]=lv;
	for(auto nxt:graph[x]){
		if(nxt.ff==p) continue;
		dfs(nxt.ff,x,nxt.ss,lv+1);
	}
}
int memo(){
	for(int i=1;i<MXH;i++){
		for(int j=1;j<=n;j++){
			par[i][j]=par[i-1][par[i-1][j]];
			min_dst[i][j]=min(min_dst[i-1][j],min_dst[i-1][par[i-1][j]]);
			max_dst[i][j]=max(max_dst[i-1][j],max_dst[i-1][par[i-1][j]]);
		}
	}
}
int min_query(int x, int y){
	int ans=INT_MAX;
	// minimum weight during level up  
	int xy=level[x]-level[y];
	for(int i=MXH-1;i>=0;i--){
		if(xy>0 && (1<<i)&xy){
			ans=min(ans,min_dst[i][x]);			
			x=par[i][x];
		}
		if(xy<0 && (1<<i)&(-xy)){
			ans=min(ans,min_dst[i][y]);			
			y=par[i][y];
		}		
	}
	if(x==y) return ans;
	// minimum weight during jump
	for(int i=MXH-1;i>=0;i--){
		if(par[i][x]!=par[i][y]){
			ans=min(ans,min(min_dst[i][x],min_dst[i][y]));
			x=par[i][x];
			y=par[i][y];
		}
	}
	return ans=min(ans,min(min_dst[0][x],min_dst[0][y]));
}
int max_query(int x, int y){
	int ans=0;
	// maximum weight during level up  
	int xy=level[x]-level[y];
	for(int i=MXH-1;i>=0;i--){
		if(xy>0 && (1<<i)&xy){
			ans=max(ans,max_dst[i][x]);
			x=par[i][x];
		}
		if(xy<0 && (1<<i)&(-xy)){
			ans=max(ans,max_dst[i][y]);
			y=par[i][y];
		}		
	}
	if(x==y) return ans;
	// maximum weight during jump
	for(int i=MXH-1;i>=0;i--){
		if(par[i][x]!=par[i][y]){
			ans=max(ans,max(max_dst[i][x],max_dst[i][y]));			
			x=par[i][x];
			y=par[i][y];
		}
	}
	return ans=max(ans,max(max_dst[0][x],max_dst[0][y]));
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z; cin>>x>>y>>z;
		graph[x].push_back({y,z});
		graph[y].push_back({x,z});
	}
	dfs(1,0,0,0);
	memo();
	int q; cin>>q;
	while(q--){
		int x,y; cin>>x>>y;
		cout<<min_query(x,y)<<" "<<max_query(x,y)<<'\n';
	}
	return 0;
}

백준 3176 도로 네트워크