import sys
input = sys.stdin.readline
from collections import deque
from math import log2
def findparent(x,d):
global minresult,maxresult
for i in range(logd+1):
if d&(1<<i):
minresult = min(minresult,mincost[i][x])
maxresult = max(maxresult,maxcost[i][x])
x = sparse[i][x]
return x
def findcoparent(x,y,c):
global minresult,maxresult
if c == 0:
if parent[x] == parent[y]:
minresult = min(minresult,mincost[0][x],mincost[0][y])
maxresult = max(maxresult,maxcost[0][x],maxcost[0][y])
else:
minresult = min(minresult,mincost[1][x],mincost[1][y])
maxresult = max(maxresult,maxcost[1][x],maxcost[1][y])
elif sparse[c][x] == sparse[c][y]:
findcoparent(x,y,c-1)
else:
minresult = min(minresult,mincost[c][x],mincost[c][y])
maxresult = max(maxresult,maxcost[c][x],maxcost[c][y])
findcoparent(sparse[c][x],sparse[c][y],c-1)
N = int(input())
graph = [[] for i in range(N)]
for _ in range(N-1):
x,y,w = map(int,input().split())
graph[x-1].append((y-1,w))
graph[y-1].append((x-1,w))
parent = [0]*N
depth = [0]*N
cost = [0]*N
dq = deque([(0,1)])
while dq:
now,d = dq.popleft()
depth[now] = d
for next,w in graph[now]:
if depth[next]:
continue
parent[next] = now
cost[next] = w
dq.append((next,d+1))
cost1 = cost[:]
cost1[0] = 1e9
logd = int(log2(d-1))
sparse = [parent]+[[0]*N for i in range(logd)]
mincost = [cost1]+[[0]*N for i in range(logd)]
maxcost = [cost]+[[0]*N for i in range(logd)]
for i in range(1,logd+1):
for n in range(N):
sparse[i][n] = sparse[i-1][sparse[i-1][n]]
mincost[i][n] = min(mincost[i-1][n],mincost[i-1][sparse[i-1][n]])
maxcost[i][n] = max(maxcost[i-1][n],maxcost[i-1][sparse[i-1][n]])
K = int(input())
for _ in range(K):
x,y = map(lambda x:x-1,map(int,input().split()))
minresult,maxresult = 1e9,0
if depth[x] > depth[y]:
x = findparent(x,depth[x]-depth[y])
elif depth[y] > depth[x]:
y = findparent(y,depth[y]-depth[x])
if x != y:
c = int(log2(depth[x]-1))
findcoparent(x,y,c)
print(minresult,maxresult)
LCA2 [백준 11438번] LCA 2 (Python3) (tistory.com) 를 활용하는 문제.
LCA2를 풀었다면 풀이는 금방 떠올릴 수 있지만 구현하는게 약간 까다로웠다.
LCA 알고리즘이 아직 익숙지 않아서 그런 것 같기도 하고...
LCA 알고리즘을 알고 있다는 가정하에 풀이를 요약하면,
1. sparse table을 3개를 만든다. 이때 부모노드에 대한 sparse, 최소cost에 대한 sparse, 최대cost에 대한 sparse이다.
2. LCA로 두 노드의 공통조상을 찾아가는 과정에서 cost에 대한 sparse를 이용해서 최솟값과 최댓값을 갱신한다.
이때 1번과정에서 cost에 대한 sparse를 만들 때, 1-1의 경로는 존재하지 않으므로 무시하기 위해서 1번에서 1번노드의 cost를 최소 cost 에서는 1e9로, 최대 cost에서는 0으로 저장하는 것이 좋다.
오늘의 교훈) LCA와 sparse table을 적재적소에 활용할 수 있도록 익숙해지자