백준 3176 - 도로 네트워크

문제 링크 : https://www.acmicpc.net/problem/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를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/%EB%B0%B1%EC%A4%80-1761-%EC%A0%95%EC%A0%90%EB%93%A4%EC%9D%98-%EA%B1%B0%EB%A6%AC

백준 1761 - 정점들의 거리

https://readytojoin.tistory.com/entry/LCA-%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%EC%B0%BE%EA%B8%B0?category=1193467

LCA - 최소 공통 조상 찾기

 

LCA 알고리즘을 사용한다. 쿼리가 많으므로 희소 배열 테크닉을 이용한다. 1761 번에서 희소 배열에 거리 합을 구한 것 처럼, 희소 배열에 경로 간 가장 짧은 도로의 길이와 가장 긴 도로의 길이 정보를 누적 저장한다.

# 3176. 도로 네트워크 ( PLATINUM 4 )
import sys
input = sys.stdin.readline
sys.setrecursionlimit(110000)

n = int(input().rstrip())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b, d = map(int, input().rstrip().split())
  graph[a].append([b, d])
  graph[b].append([a, d])

depth = [0 for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
parent = [[-1, 0] for _ in range(n+1)]

def dfs(now, p, dep, pre_dist):
  global depth
  global visited
  global parent

  depth[now] = dep
  
  for next, dist in graph[now]:
    if visited[next] == 0:
      visited[next] = 1
      dfs(next, now, dep + 1, dist)

  parent[now] = [p, pre_dist]

for i in range(1, n+1):
  if visited[i] == 0:
    visited[i] = 1
    dfs(i, -1, 0, 0)

root = -1
for i in range(1, n+1):
  if parent[i][0] == -1:
    root = i
    break

table = [[[0, 0, 0] for _ in range(n+1)] for _ in range(21)]
for i in range(1, n+1): table[0][i] = [parent[i][0], parent[i][1], parent[i][1]]

for i in range(1, 21):
  for j in range(1, n+1):
    table[i][j] = [table[i-1][table[i-1][j][0]][0], min(table[i-1][table[i-1][j][0]][1], table[i-1][j][1]), max(table[i-1][table[i-1][j][0]][2], table[i-1][j][2])]

def lca(a, b):
  if depth[a] < depth[b]:
    a, b = b, a

  res_min = -1
  res_max = -1
  for i in range(20, -1, -1):
    if depth[a] - depth[b] >= (1 << i):
      a, min_cost, max_cost = table[i][a]
      if res_min == -1: res_min = min_cost
      else: res_min = min(res_min, min_cost)
      if res_max == -1: res_max = max_cost
      else: res_max = max(res_max, max_cost)

  if a == b:
    return [res_min, res_max]
  else:
    for i in range(20, -1, -1):
      if table[i][a][0] != table[i][b][0]:
        a, min_cost1, max_cost1 = table[i][a]
        b, min_cost2, max_cost2 = table[i][b]
        if res_min == -1: res_min = min(min_cost1, min_cost2)
        else: res_min = min(res_min, min(min_cost1, min_cost2))
        if res_max == -1: res_max = max(max_cost1, max_cost2)
        else: res_max = max(res_max, max(max_cost1, max_cost2))

    if res_min == -1: res_min = min(table[0][a][1], table[0][b][1])
    else: res_min = min(res_min, min(table[0][a][1], table[0][b][1]))
    if res_max == -1: res_max = max(table[0][a][2], table[0][b][2])
    else: res_max = max(res_max, max(table[0][a][2], table[0][b][2]))
    return [res_min, res_max]

m = int(input().rstrip())
for _ in range(m):
  a, b = map(int, input().rstrip().split())
  print(' '.join(map(str, lca(a, b))))