[Python] 백준 - 3176 도로 네트워크

문제

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.

다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

출력

총 K개 줄에 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

 

문제해결방법

 

1. LCA알고리즘의 작동원리만 모형적으로 이해가 되면, 거기에 min, max 갱신만 얹어준다는 생각이 가능하다.

 

아래 포스팅에서 LCA알고리즘의 모형을 보도록 하자.

[Python] 백준 - 11438 LCA 2

 

- 코드 

import sys
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(idx, dep):
	v[idx] = 1
	depth[idx] = dep
	for next, lth in graph[idx]:
		if v[next] == 0:
			dp[0][next][0] = idx
			dp[0][next][1] = lth
			dp[0][next][2] = lth
			dfs(next, dep+1)

def Makedp():
	dfs(1, 0)
	for i in range(1, log):
		for j in range(1, n+1):
			dp[i][j][0] = dp[i-1][dp[i-1][j][0]][0]
			dp[i][j][1] = min(dp[i-1][dp[i-1][j][0]][1], dp[i-1][j][1])
			dp[i][j][2] = max(dp[i-1][dp[i-1][j][0]][2], dp[i-1][j][2])
	return

def LCA(a, b):
	M, m = 0, sys.maxsize
	if depth[a] < depth[b]:
		a, b = b, a
	for i in range(log-1, -1, -1):
		if (depth[a]-depth[b]) >= (1 << i):
			M = max(M, dp[i][a][2])
			m = min(m, dp[i][a][1])
			a = dp[i][a][0]
	if a == b:
		return (m, M)
	for i in range(log-1, -1, -1):
		if dp[i][a][0] != dp[i][b][0]:
			M = max(M, dp[i][a][2], dp[i][b][2])
			m = min(m, dp[i][a][1], dp[i][b][1])
			a = dp[i][a][0]
			b = dp[i][b][0]
	M = max(M, dp[0][a][2], dp[0][b][2])
	m = min(m, dp[0][a][1], dp[0][b][1])
	return (m, M)
			

n = int(input())
log = int(math.log2(100000))+1
graph = [[] for _ in range(n+1)]
v = [0 for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
dp = [[[0, 0, 0] for _ in range(n+1)] for _ in range(log)]
for _ in range(n-1):
	a, b, c = map(int, input().split())
	graph[a].append((b, c))
	graph[b].append((a, c))
Makedp()
m = int(input())
for _ in range(m):
	a, b = map(int, input().split())
	ans = LCA(a, b)
	print(*ans)