문제
KOI 도시는
즉, 도시의 도로망은 트리 구조를 이룬다. 도로는 2차원 평면 상에 있으며, 두 도로가 끝점을 제외한 위치에서 교차하지 않는다.
각 도로에는
KOI 도시는 몇십년 전까지만 하여도 작은 마을이었지만, 사람이 유입되고 크기가 커지면서 급격히 팽창하기 시작하였다.
급격한 팽창 과정에서 시장은 행정 편의를 위해 교차로에
이 때 번호 시스템은 다음과 같은 성질을 만족한다.
• 1번 교차로는 도시의 중심으로, 2개 이상의 도로와 인접함이 보장된다.
• 교차로에 매겨진 번호는 1번 교차로를 루트로 한 트리의 전위 순회 순서 (Preorder) 중 하나이다.
• 모든 교차로에 대해서, 인접한 도로로 직접 연결된) 교차로 중 가장 번호가 작은 교차로를 생각해 보자.
이 교차로를 기준으로 시계 반대 방향으로 인접한 교차로의 번호를 나열했을 때, 번호는 증가한다.
KOI 도시에 많은 사람들이 유입되면서, 교통 체증 문제가 심화되었다. 시장은 이를 해결하기 위해 교통 인프라가 가장 빈약한 도시들을 외곽 순환 도로로 이었다. KOI 도시에 있는 모든 교차로 중, 단
당신은 KOI 도시의 내비게이션 시스템을 구축하려고 한다. 내비게이션 시스템은,
도로망 구조가 주어졌을 때,
제약 조건
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
입력
첫 번째 줄에 KOI 도시의 교차로 수
이후
외곽 순환 도로 건설 전
다음 줄에,
다음 줄에 질의의 수
이후
출력
Q 개의 줄에 걸쳐, u번 교차로와 v번 교차로를 잇는 경로들 중 가중치 합의 최솟값을 하나의 정수로 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 6점 | u = 1 |
| #2 | 8점 | 모든 1 ≤ i ≤ N-1에 대해 pi = 1. |
| #3 | 5점 | 모든 1 ≤ i ≤ N-1에 대해 i ≤ 106, 모든 1 ≤ i ≤ k 에 대해 wi = 1012. |
| #4 | 15점 | 모든 1 ≤ i ≤ k 에 대해 wi = 0. |
| #5 | 57점 | 4개 이상의 도로와 인접한 교차로가 존재하지 않음. |
| #6 | 9점 | 추가 제약 조건 없음. |
예제1
4
19
18
10
999
6
12
13
14
23
24
34
9
8
0
9
9
8
예제2
11
19
18
30
47
41
36
10
87
81
106
000000
21
12
13
14
15
16
17
18
19
110
111
71
82
93
104
115
16
27
38
49
510
611
7
8
8
7
7
7
0
7
1
7
7
7
1
7
0
7
0
8
1
6
0
예제3
11
19
18
30
47
41
36
10
87
81
106
100000000000010000000000001000000000000100000000000010000000000001000000000000
21
12
13
14
15
16
17
18
19
110
111
71
82
93
104
115
16
27
38
49
510
611
9
8
8
15
9
14
0
7
1
7
14
9
15
9
22
9
23
8
15
16
16