외곽 순환 도로

문제

KOI 도시는 $NN$ 개의 교차로와 $N-1N\; -\; 1$ 개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 교차로를 도로만을 사용하여 오갈 수 있다. 즉, 도시의 도로망은 트리 구조를 이룬다. 도로는 2차원 평면 상에 있으며, 두 도로가 끝점을 제외한 위치에서 교차하지 않는다. 각 도로에는 $00$ 이상의 정수 가중치가 존재하며, 이 가중치는 각 도로를 이용하는 데 걸리는 시간을 의미한다.

KOI 도시는 몇십년 전까지만 하여도 작은 마을이었지만, 사람이 유입되고 크기가 커지면서 급격히 팽창하기 시작하였다. 급격한 팽창 과정에서 시장은 행정 편의를 위해 교차로에 $11$ 이상 $NN$ 이하의 번호를 매겼다. 이 때 번호 시스템은 다음과 같은 성질을 만족한다.

• $11$번 교차로는 도시의 중심으로, $22$개 이상의 도로와 인접함이 보장된다.
• 교차로에 매겨진 번호는 $11$번 교차로를 루트로 한 트리의 전위 순회 순서 (Preorder) 중 하나이다.
• 모든 교차로에 대해서, 인접한 (도로로 직접 연결된) 교차로 중 가장 번호가 작은 교차로를 생각해 보자. 이 교차로를 기준으로 시계 반대 방향으로 인접한 교차로의 번호를 나열했을 때, 번호는 증가한다.

KOI 도시에 많은 사람들이 유입되면서, 교통 체증 문제가 심화되었다. 시장은 이를 해결하기 위해 교통 인프라가 가장 빈약한 도시들을 외곽 순환 도로로 이었다. KOI 도시에 있는 모든 교차로 중, 단 $11$개의 도로와 인접한 교차로들의 번호를 증가하는 순서대로 나열한 리스트를 $v_1,v_2,\dots ,v_k\{v\_1,\; v\_2,\; \backslash dots\; ,\; v\_k\}$ 라고 하자. 시장은, 모든 1 ≤ i ≤ k 에 대해서, $v_{i}v\_i$번 교차로와 $v_{(i(\mathrm{m}\mathrm{o}\mathrm{d}k))+1}v\_\{(i\; \backslash pmod\; k)+1\}$번 교차로를 잇는 양방향 도로를 건설하였다. 각 도로의 가중치는 $00$ 이상의 정수 $w_{i}w\_i$ 이며, 이는 입력으로 주어진다. 번호 시스템의 특성상, 두 도로가 끝점을 제외한 위치에서 교차하지 않게끔 외곽 순환 도로를 이을 수 있음을 관찰하면 좋다.

당신은 KOI 도시의 내비게이션 시스템을 구축하려고 한다. 내비게이션 시스템은, $QQ$개의 질의 $uu$, $vv$가 주어졌을 때, $uu$번 교차로에서 $vv$번 교차로로 이동하는 데 걸리는 최소 시간을 출력해야 한다. $uu$번 교차로에서 $vv$번 교차로로 이동하는 데 걸리는 최소 시간은, $uu$번 교차로와 $vv$번 교차로를 잇는 경로들 중 가중치 합의 최솟값과 같다.

도로망 구조가 주어졌을 때, $QQ$개의 질의를 효율적으로 응답하는 프로그램을 작성하여라.

입력

첫 번째 줄에 KOI 도시의 교차로 수 $NN$이 주어진다.

이후 $N-1N\; -\; 1$개의 줄이 주어진다. 이 중 $ii$번째 줄에는, 두 정수 $p_{i}p\_i$, $c_{i}c\_i$ 가 공백으로 구분되어 주어진다. 이는, 교차로 $p_{i}p\_i$와 교차로 $i+1i\; +\; 1$를 잇는 가중치 $c_{i}c\_i$의 양방향 도로가 존재함을 뜻한다.

외곽 순환 도로 건설 전 $11$개의 도로와 인접한 교차로의 수를 $kk$라고 하고, $11$개의 도로와 인접한 교차로들의 번호를 증가하는 순서대로 나열한 리스트를 $v_1,v_2,\dots ,v_k\{v\_1,\; v\_2,\; \backslash dots\; ,\; v\_k\}$ 라고 하자. 다음 줄에, $kk$개의 정수 $w_1,w_2,\dots ,w_{k}w\_1,\; w\_2,\; \backslash dots\; ,\; w\_k$가 공백으로 구분되어 주어진다. 이는, 외곽 순환 도로의 $v_{i}v\_i$번 교차로와 $v_{i(\mathrm{m}\mathrm{o}\mathrm{d}k)+1}v\_\{i\; \backslash pmod\; k+1\}$번 교차로를 잇는 양방향 도로의 가중치가 $w_{i}w\_i$임을 뜻한다.

다음 줄에 질의의 수 $QQ$가 주어진다.

이후 $QQ$개의 줄에 최소 시간을 알고 싶은 두 교차로의 번호 $uu$, $vv$가 주어진다.

출력

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

4
1 9
1 8
1 0
9 9 9
6
1 2
1 3
1 4
2 3
2 4
3 4

9
8
0
9
9
8

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
0 0 0 0 0 0
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

7
8
8
7
7
7
0
7
1
7
7
7
1
7
0
7
0
8
1
6
0

11
1 9
1 8
3 0
4 7
4 1
3 6
1 0
8 7
8 1
10 6
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
21
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
7 1
8 2
9 3
10 4
11 5
1 6
2 7
3 8
4 9
5 10
6 11

9
8
8
15
9
14
0
7
1
7
14
9
15
9
22
9
23
8
15
16
16