60057 외곽 순환 도로 Diamond IV

문제

N개의 교차로가 트리 구조로 연결되어 있다. 리프 노드들이 전위 순회 순서로 원형 도로로 추가 연결된다. Q개의 쿼리에 대해 두 교차로 사이 최단 거리를 구하시오.

입력

첫째 줄에 N이 주어진다. 다음 N-1줄에 간선 정보 (부모, 가중치)가 주어진다. 다음 줄에 Q, 다음 Q줄에 u, v가 주어진다.

출력

각 쿼리의 최단 거리.