[Python]최소공통조상 백준 3176

   문제

   https://www.acmicpc.net/problem/3176

이 문제는 최소공통조상을 구해서 각 도시에서 최소공통조상까지  가장짧은 도로의 

길이와 가장긴 도록의 길이를 구하는 문제이다.문제에서 볼 수 있듯이 모든 도시의

 쌍에 그 도시를 연결하는 유일한 통로가 있다고 하였기 때문에 사이클이 없는 트리

 구조이다.먼저 입력을 통해 얻은정보로 DFS를 통해 아무노드나 루트로 하는 트리 

구조를 만들어준다.

만들어진 트리를 바탕으로 희소테이블도 만들어준다.

이때 최소값 최대값도 같이 저장시켜주는게 저번 문제와 다른 점이다.

2^k번째 부모노드와 그 부모노드까지의 가장짧은 도로와 가장 긴 도로의 길이도 같이

 저장해준다.이렇게 만들어진 희소테이블을 이용해 두 도시의 레벨을 맞춰주고

 최소공통조상을 찾는다.이때도 가장 짧은 도로와 가장 긴 도로의 길이를 업데이트 

시켜주면서 진행하면 된다.

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
#아무 노드나 루트로 잡고 부모노드 저장
 
# print(p_list)
 
#2^k번째 부모 노드와 가장 짧은 도로 가장 긴도로 구하기
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
    # print(depth[D])
    # print(depth[E])
    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)