백준3176 도로 네트워크

작성일 | In

문제 링크

  • http://icpc.me/3176

문제 출처

  • 2006 COI Final Exam #2 2번

사용 알고리즘

  • LCA

시간복잡도

  • 전처리 O(NlogN)
  • 쿼리 O(logN)

풀이

lca를 구하기 위한 sparse table을 만들면서, 동시에 최댓값과 최솟값도 같이 저장해줍시다.
자세한 구현은 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int chk[101010];
int dep[101010];
int dist[101010];
int dp[101010][22];
int mn[101010][22];
int mx[101010][22];
vector<p> g[101010];
int n;

void dfs(int now, int d, int c){
	chk[now] = 1;
	dep[now] = d;
	dist[now] = c;
	for(auto i : g[now]){
		int nxt = i.x;
		int cst = i.y;
		if(chk[nxt]) continue;
		dp[nxt][0] = now;
		mn[nxt][0] = mx[nxt][0] = cst;
		dfs(nxt, d+1, c+cst);
	}
}

p lca(int u, int v){
	int l = 1e9+7;
	int r = -l;
	if(dep[u] > dep[v]) swap(u, v);
	int diff = dep[v] - dep[u];
	for(int i=0; diff; i++){
		if(diff & 1){
			l = min(l, mn[v][i]);
			r = max(r, mx[v][i]);
			v = dp[v][i];
		}
		diff >>= 1;
	}
	if(u == v) return {l, r};
	for(int i=21; i>=0; i--){
		if(dp[u][i] != dp[v][i]){
			l = min({l, mn[u][i], mn[v][i]});
			r = max({r, mx[u][i], mx[v][i]});
			u = dp[u][i], v = dp[v][i];
		}
	}
	l = min({l, mn[u][0], mn[v][0]});
	r = max({r, mx[u][0], mx[v][0]});
	return {l, r};
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=0; i<n-1; i++){
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	dfs(1, 0, 0);

	for(int j=1; j<22; j++){
		for(int i=1; i<=n; i++){
			dp[i][j] = dp[dp[i][j-1]][j-1];
			mn[i][j] = min(mn[i][j-1], mn[dp[i][j-1]][j-1]);
			mx[i][j] = max(mx[i][j-1], mx[dp[i][j-1]][j-1]);
		}
	}

	int m; cin >> m;
	while(m--){
		int a, b; cin >> a >> b;
		auto t = lca(a, b);
		cout << t.x << " " << t.y << "\n";
	}
}