외곽 순환 도로

KOI 도시는 $N$개의 교차로와 $N - 1$개의 양방향 도로로 이루어져 있다. 임의의 두 교차로는 도로만 사용해서 오갈 수 있으므로 도로망은 트리 구조이다. 도로는 2차원 평면 위에 놓여 있고, 두 도로는 끝점이 아닌 곳에서 교차하지 않는다. 각 도로에는 0 이상의 정수 가중치가 있으며, 이 가중치는 그 도로를 이용하는 데 걸리는 시간이다.

KOI 도시는 몇십 년 전까지만 해도 작은 마을이었지만, 사람이 유입되면서 크기가 급격히 커졌다. 시장은 행정 편의를 위해 교차로에 1 이상 $N$ 이하의 번호를 매겼다. 번호 체계는 다음 성질을 만족한다.

• 1번 교차로는 도시의 중심이며, 2개 이상의 도로와 인접함이 보장된다.
• 교차로 번호는 1번 교차로를 루트로 한 트리의 전위 순회(preorder) 순서 중 하나이다.
• 모든 교차로에 대해, 직접 연결된 교차로 중 번호가 가장 작은 교차로를 기준으로 시계 반대 방향으로 인접한 교차로들의 번호를 나열하면 번호가 증가한다.

교통 체증이 심해지자 시장은 교통 인프라가 가장 빈약한 곳들을 외곽 순환 도로로 이었다. 도로 1개와만 인접한 교차로들의 번호를 증가하는 순서로 나열한 리스트를 ${v_1, v_2, \dots, v_k}$라고 하자. 시장은 모든 $1 ≤ i ≤ k$에 대해 $v_i$번 교차로와 $v_{(i \bmod k)+1}$번 교차로를 잇는 양방향 도로를 건설하였다. 각 외곽 도로의 가중치 $w_i$는 0 이상의 정수이며 입력으로 주어진다. 번호 체계의 특성상 두 도로가 끝점 외에서 교차하지 않도록 외곽 순환 도로를 이을 수 있음을 관찰하면 좋다.

KOI 도시의 내비게이션 시스템을 구축하려고 한다. $Q$개의 질의 $u$, $v$가 주어지면 $u$번 교차로에서 $v$번 교차로로 이동하는 데 걸리는 최소 시간을 출력해야 한다. 이 시간은 두 교차로를 잇는 경로들 중 가중치 합의 최솟값이다. 도로망 구조가 주어졌을 때 $Q$개의 질의에 효율적으로 답하는 프로그램을 작성하라.

첫 줄에 교차로 수 $N$이 주어진다.

이후 $N - 1$개의 줄이 주어진다. 이 중 $i$번째 줄에는 두 정수 $p_i$, $c_i$가 공백으로 구분되어 주어진다. 이는 교차로 $p_i$와 교차로 $i + 1$을 잇는 가중치 $c_i$의 양방향 도로가 있음을 뜻한다.

외곽 순환 도로를 건설하기 전에 도로 1개와만 인접한 교차로의 수를 $k$라 하고, 그 번호를 증가하는 순서로 나열한 리스트를 ${v_1, v_2, \dots, v_k}$라고 하자. 다음 줄에 $k$개의 정수 $w_1, w_2, \dots, w_k$가 공백으로 구분되어 주어진다. 이는 외곽 순환 도로에서 $v_i$번 교차로와 $v_{i \bmod k+1}$번 교차로를 잇는 도로의 가중치가 $w_i$임을 뜻한다.

다음 줄에 질의의 수 $Q$가 주어진다. 이후 $Q$개의 줄에 최소 시간을 알고 싶은 두 교차로의 번호 $u$, $v$가 주어진다.

$Q$개의 줄에 걸쳐 $u$번 교차로와 $v$번 교차로를 잇는 경로들 중 가중치 합의 최솟값을 정수 하나로 출력한다.

• $4 ≤ N ≤ 100,000$
• $1 ≤ p_i ≤ i$
• $0 ≤ c_i, w_i ≤ 10^{12}$
• $1 ≤ Q ≤ 250,000$
• $1 ≤ u, v ≤ N$, $u ≠ v$