BOJ 3176 - 도로 네트워크 (LCA)

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

유독 LCA 코드를 짤 때 오타를 많이 내는것 같다. 

 

<문제설명>

최대크기 1e5인 간선 가중치가 있는 트리가 주어질 때, 1e5개의 쿼리에 답하는 문제.

쿼리 u, v : 정점u,v 사이의 경로 중 간선의 최소값과 최대값을 출력.

 

<풀이>

u,v사이의 경로는 유일하다. 쿼리에 log(n)만에 답해야 한다. 

 

lca(u,v) 에서 u,v를 올려줄 때 그 과정을 따라가면서 간선 가중치 최소, 최대값(mn,mx)를 갱신할 것이기 때문에 depth를 이용하는 코드를 사용할 것이다.

 

lca알고리즘을 다시 떠올려보자. u,v중 깊이가 더 깊은 정점을 u라고 강제하고, 

1. u의 깊이를 v의 깊이에 맞춰 올려준다.

2. 같아진 u,v 깊이를 lca 직전까지 끌어올려준다. p[u][0]이 바로 최소공통조상이다.

 

minl[i][j], maxl[i][j]를 각각 정점i~i의 (1<<j)번째 부모사이의 최소 간선길이, 최대 간선길이라고 하자.

dfs할때 p배열을 초기화 하면서 minl, maxl도 같이 초기화해준다. (dfs할땐 부모정점에 대해서 모두 초기화 된 상태이므로 그때그때 초기화해도 무방함.)

 

lca 함수에서 p,minl,maxl을 바탕으로 경로의 간선길이의 최소값,최대값을 구한다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1e5 + 5;
typedef pair<int, int> P;

int depth[MAX], p[MAX][20], minl[MAX][20], maxl[MAX][20], n;
vector<P> adj[MAX];

void dfs(int curr, int prv) {
	for (P pp : adj[curr]) {
		int next = pp.first, wgt = pp.second;
		if (next != prv) {
			minl[next][0] = maxl[next][0] = wgt;
			p[next][0] = curr;
			for (int i = 1; (1<<i) < n; i++) {
				p[next][i] = p[p[next][i - 1]][i - 1];
                //i ~ i의 (1<<j)번째 사이의 최소, 최대값은
                //minmax(i ~ i의 (1<<(j-1))번째 최소/최대,  i의 (1<<(j-1))번째 ~ i의 (1<<j)번째)
				minl[next][i] = min(minl[next][i - 1], minl[p[next][i - 1]][i - 1]);
				maxl[next][i] = max(maxl[next][i - 1], maxl[p[next][i - 1]][i - 1]);
			}			
			depth[next] = depth[curr] + 1;
			dfs(next, curr);
		}
	}
}

int mn, mx;
void lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
    int log
    for(log=1; (1<<log)<=depth[u]; log++);
    log--;

	for (int i = log; i >= 0; i--) {
		if (depth[u] - (1 << i) >= depth[v]) {
			mn = min(mn, minl[u][i]);
			mx = max(mx, maxl[u][i]);
			u = p[u][i];
		}
	}
	if (u == v) return;

	for (int i = log; i >= 0; i--) {
		if (p[u][i] != 0 && p[v][i] != 0) {
			if (p[u][i] != p[v][i]) {
				mn = min(mn, min(minl[u][i], minl[v][i]));
				mx = max(mx, max(maxl[u][i], maxl[v][i]));
				u = p[u][i];
				v = p[v][i];
			}
		}
	}
	mn = min(mn, min(minl[u][0], minl[v][0]));
	mx = max(mx, max(maxl[u][0], maxl[v][0]));
	return;
}

int main() {
	FAST;
	cin >> n;
	for (int i = 0, u, v, w; i < n - 1; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
		adj[v].push_back({ u,w });
	}
	dfs(1, 0);
	int q; cin >> q;
	while (q--) {
		int a, b; cin >> a >> b;
		mn = 1e9, mx = 0;
		lca(a, b);
		cout << mn << " " << mx << '\n';
	}
}

 

 

<생각>

lca 알고리즘의 과정을 모두 완전히 이해해야만 풀 수 있었던 문제라고 생각함.

 

lca에서 log를 구하는 것이나 dfs에서 p배열 초기화할때 (1<<i) <n 대신에 그냥 19로 대체해도 된다.