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

도시가 $N$개 존재하고 도로가 $N-1$개 존재하므로 트리 형태인 것을 알 수 있다. 따라서 경로를 찾기 위해서는 최소 공통 조상 알고리즘을 사용하고, 빠르게 찾기 위해 희소 배열을 사용한다.

이 문제에서는 경로 상에서 가장 짧은 도로와 가장 긴 도로를 찾아내야 하므로 각각 배열로 만들어 갱신해야 한다.

import sys
input = sys.stdin.readline


def make_tree():
    que = [1]
    # bfs로 순회하면서 희소 배열을 생성한다.
    for node in que:
        visit[node] = 1
        for i in range(1, 17):
            if not parent[i-1][node]:
                break
            parent[i][node] = parent[i-1][parent[i-1][node]]
            # 2^i 번째 조상까지 연결된 도로의 최소, 최대
            min_edge[i][node] = min(min_edge[i-1][node], min_edge[i-1][parent[i-1][node]])
            max_edge[i][node] = max(max_edge[i-1][node], max_edge[i-1][parent[i-1][node]])
        for b, c in graph[node]:
            if visit[b]:
                continue
            # 자식 노드의 1번째 조상은 node임
            parent[0][b] = node
            min_edge[0][b] = c
            max_edge[0][b] = c
            depth[b] = depth[node]+1
            que.append(b)
        
def find_lca(a, b):
    min_res = 1_000_001
    max_res = 0
    # depth[a] > depth[b]를 항상 유지한다.
    a, b = (a, b) if depth[a] >= depth[b] else (b, a)
    # 두 노드의 깊이를 일치시킨다.
    while depth[a] != depth[b]:
        for i in range(1, 18):
        	# 조상이 없거나 깊이가 얕아지는 경우 그 이전 조상으로 이동한다.
            if not parent[i][a] or depth[parent[i][a]] < depth[b]:
                min_res = min(min_res, min_edge[i-1][a])
                max_res = max(max_res, max_edge[i-1][a])
                a = parent[i-1][a]
                break
    if a == b:
        return (min_res, max_res)
    # 공통 조상을 찾을 때 최소한으로 올라가야 하므로 부모가 같으면 바로 종료한다.
    while parent[0][a] != parent[0][b]:
        for i in range(1, 18):
        	# 조상이 같은 경우에는 최소한으로 올라왔는지 알 수 없다.
            if not parent[i][a] or parent[i][a] == parent[i][b]:
                min_res = min(min_res, min_edge[i-1][a], min_edge[i-1][b])
                max_res = max(max_res, max_edge[i-1][a], max_edge[i-1][b])
                a = parent[i-1][a]
                b = parent[i-1][b]
                break
    min_res = min(min_res, min_edge[0][a], min_edge[0][b])
    max_res = max(max_res, max_edge[0][a], max_edge[0][b])
    return (min_res, max_res)

n = int(input())
graph = [[] for _ in range(n+1)]
visit = [0]*(n+1)
min_edge = [[1_000_001]*(n+1) for _ in range(18)]
max_edge = [[0]*(n+1) for _ in range(18)]
parent = [[0]*(n+1) for _ in range(18)]
depth = [0]*(n+1)
depth[1] = 1
for _ in range(n-1):
    a, b, c = map(int, input().rstrip().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

make_tree()
k = int(input())
for _ in range(k):
    a, b = map(int, input().rstrip().split())
    print(*find_lca(a, b))