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

Tree + Dynamic Programming

문제

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를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

---

import sys
from collections import deque
from math import log2
INF=sys.maxsize
 
 
N=int(sys.stdin.readline())
tree=[[] for _ in range(N+1)]
depth=[0 for _ in range(N+1)]
logN=int(log2(N)+1)
for _ in range(N-1):
    A,B,C=map(int,sys.stdin.readline().split())
    tree[A].append([B,C])
    tree[B].append([A,C])
 
 
#DFS
p_list=[[0,0] for _ in range(N+1)]
p_check=[True for _ in range(N+1)]
q=deque()
q.append(1)
p_check[1]=False
while q:
    a=q.popleft()
    for b,c in tree[a]:
        if p_check[b]:
            q.append(b)
            depth[b]=depth[a]+1
            p_check[b]=False
            p_list[b][0]=a
            p_list[b][1]=c
 
DP=[[[0,0,0] for _ in range(logN)] for _ in range(N+1)]

for i in range(N+1):
    DP[i][0][0]=p_list[i][0]
    DP[i][0][1]=p_list[i][1]
    DP[i][0][2]=p_list[i][1]
 

for j in range(1,logN):
    for i in range(1,N+1):
        DP[i][j][0]=DP[DP[i][j-1][0]][j-1][0]
        DP[i][j][1]=min(DP[i][j-1][1],DP[DP[i][j-1][0]][j-1][1])
        DP[i][j][2]=max(DP[i][j-1][2],DP[DP[i][j-1][0]][j-1][2])
 
 
K=int(sys.stdin.readline())
for _ in range(K):
    D,E=map(int,sys.stdin.readline().split())
    if depth[D]<depth[E]:
        D,E=E,D

    dif=depth[D]-depth[E]
    shortest=INF
    longest=0

    for i in range(logN):
        if dif & 1<<i:
            shortest=min(shortest,DP[D][i][1])
            longest=max(longest,DP[D][i][2])
            D=DP[D][i][0]
 
    if D==E:
        print(shortest,longest)
        continue
 

    for i in range(logN-1,-1,-1):
        if DP[D][i][0]!=DP[E][i][0]:
            shortest=min(shortest,DP[D][i][1],DP[E][i][1])
            longest=max(longest,DP[D][i][2],DP[E][i][2])
            D=DP[D][i][0]
            E=DP[E][i][0]
    shortest = min(shortest, DP[D][i][1], DP[E][i][1])
    longest = max(longest, DP[D][i][2], DP[E][i][2])
    print(shortest,longest)

쉽지 않은 난이도. 두고두고 공부해야 할 문제.

참고)
https://developmentdiary.tistory.com/470
https://devowen.com/274