J - 道路ネットワークの整備 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は、N 個の都市からなる道路ネットワークの管理を任されています。

このネットワークは根付き木の構造をしており、都市 1 が首都（根）です。都市 i（2 \leq i \leq N）にはそれぞれ親都市 P_i（P_i < i）が定まっており、都市 i と親都市 P_i を直接結ぶ道路がちょうど 1 本存在します。この道路を道路 i と呼ぶことにします。道路 i には、交通負荷への耐性を表す耐久値が設定されており、初期耐久値は W_i です。道路は全部で N - 1 本あり、木構造であるため、任意の 2 都市間を結ぶ経路（同じ都市を 2 度通らない道路の列）はちょうど 1 通りに定まります。

高橋君は、道路の補強工事を Q 回行います。j 回目（1 \leq j \leq Q）の補強工事では、2 つの都市 u_j, v_j を指定し、都市 u_j と都市 v_j を結ぶ経路上にあるすべての道路の耐久値をそれぞれ 1 増加させます。u_j = v_j の場合は経路上に道路が存在しないため、何も変化しません。同じ道路に対して複数回の補強工事が適用されることもあり、そのたびに耐久値が 1 ずつ加算されます。

Q 回の補強工事をすべて行った後、青木君が道路ネットワークの状態について R 個の質問をします。k 番目（1 \leq k \leq R）の質問では、2 つの都市 a_k, b_k を指定し、都市 a_k と都市 b_k を結ぶ経路上にあるすべての道路の耐久値のうち、最小値を求めます。ただし、a_k = b_k の場合は経路上に道路が存在しないため、答えは 0 とします。

すべての補強工事を行った後の道路ネットワークに対して、各質問に答えてください。

制約

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq P_i \leq i - 1（2 \leq i \leq N）
  • 0 \leq W_i \leq 10^9（2 \leq i \leq N）
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq u_j, v_j \leq N（1 \leq j \leq Q）
  • 1 \leq R \leq 5 \times 10^4
  • 1 \leq a_k, b_k \leq N（1 \leq k \leq R）
  • 入力はすべて整数である。
  • 各質問の答えは 2^{63} - 1 以下であることが保証される。

入力

N
P_2 W_2
P_3 W_3
\vdots
P_N W_N
Q
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q
R
a_1 b_1
a_2 b_2
\vdots
a_R b_R
  • 1 行目には、都市の数 N が与えられる。
  • 続く N - 1 行には、都市 2, 3, \ldots, N に対応する情報が順に与えられる。このうち都市 i（2 \leq i \leq N）に対応する行には、親都市 P_i と、道路 i（都市 i とその親都市 P_i を結ぶ道路）の初期耐久値 W_i が、スペース区切りで与えられる。
  • 次の行には、補強工事の回数 Q が与えられる。
  • 続く Q 行の j 行目（1 \leq j \leq Q）には、j 回目の補強工事で指定される都市の組 u_j, v_j が、スペース区切りで与えられる。
  • 次の行には、質問の数 R が与えられる。
  • 続く R 行の k 行目（1 \leq k \leq R）には、k 番目の質問で指定される都市の組 a_k, b_k が、スペース区切りで与えられる。

出力

R 行出力せよ。k 行目（1 \leq k \leq R）には、k 番目の質問に対する答えを出力せよ。すなわち、a_k \neq b_k の場合は都市 a_k と都市 b_k を結ぶ経路上にあるすべての道路の耐久値の最小値を、a_k = b_k の場合は 0 を出力せよ。

入力例 1

5
1 3
1 5
2 2
2 4
3
4 3
5 4
1 1
4
4 3
5 3
2 2
1 5

出力例 1

4
4
0
4

入力例 2

3
1 1000000000
1 0
2
2 3
1 1
3
2 3
1 2
3 3

出力例 2

1
1000000001
0

入力例 3

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

出力例 3

4
4
1
6
0
4
1

入力例 4

25
1 100
1 50
2 70
2 30
3 80
3 60
4 20
4 90
5 10
5 40
6 55
6 65
7 75
7 85
8 15
8 25
9 35
10 45
11 5
12 95
13 0
14 110
15 120
18 33
22
16 25
20 21
22 24
17 19
1 25
8 15
10 14
23 5
12 12
2 18
3 20
21 24
16 17
25 22
11 13
4 7
19 24
1 1
18 20
6 25
14 22
9 23
18
16 24
20 22
1 25
12 23
17 17
2 15
19 21
25 24
8 18
10 11
3 22
5 23
6 14
7 21
11 25
1 1
4 20
13 24

出力例 4

17
3
37
57
0
61
13
37
23
13
3
38
69
57
37
0
8
69

入力例 5

1
1
1 1
1
1 1

出力例 5

0

Score : 433 pts

Problem Statement

Takahashi is in charge of managing a road network consisting of N cities.

This network has the structure of a rooted tree, with city 1 being the capital (root). Each city i (2 \leq i \leq N) has a designated parent city P_i (P_i < i), and there exists exactly one road directly connecting city i and its parent city P_i. We will call this road road i. Road i has a durability value representing its resistance to traffic load, with an initial durability value of W_i. There are N - 1 roads in total, and since the structure is a tree, the path (a sequence of roads not passing through the same city twice) connecting any two cities is uniquely determined.

Takahashi performs Q reinforcement operations on the roads. In the j-th (1 \leq j \leq Q) reinforcement operation, he specifies two cities u_j, v_j and increases the durability value of every road on the path connecting city u_j and city v_j by 1. If u_j = v_j, there are no roads on the path, so nothing changes. The same road may have multiple reinforcement operations applied to it, and each time its durability value is incremented by 1.

After all Q reinforcement operations are completed, Aoki asks R questions about the state of the road network. In the k-th (1 \leq k \leq R) question, he specifies two cities a_k, b_k and asks for the minimum value among the durability values of all roads on the path connecting city a_k and city b_k. However, if a_k = b_k, there are no roads on the path, so the answer is 0.

Answer each question based on the road network after all reinforcement operations have been performed.

Constraints

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
  • 0 \leq W_i \leq 10^9 (2 \leq i \leq N)
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq u_j, v_j \leq N (1 \leq j \leq Q)
  • 1 \leq R \leq 5 \times 10^4
  • 1 \leq a_k, b_k \leq N (1 \leq k \leq R)
  • All input values are integers.
  • It is guaranteed that the answer to each question is at most 2^{63} - 1.

Input

N
P_2 W_2
P_3 W_3
\vdots
P_N W_N
Q
u_1 v_1
u_2 v_2
\vdots
u_Q v_Q
R
a_1 b_1
a_2 b_2
\vdots
a_R b_R
  • The first line gives the number of cities N.
  • The following N - 1 lines give information corresponding to cities 2, 3, \ldots, N in order. The line corresponding to city i (2 \leq i \leq N) gives the parent city P_i and the initial durability value W_i of road i (the road connecting city i and its parent city P_i), separated by a space.
  • The next line gives the number of reinforcement operations Q.
  • The j-th (1 \leq j \leq Q) of the following Q lines gives the pair of cities u_j, v_j specified in the j-th reinforcement operation, separated by a space.
  • The next line gives the number of questions R.
  • The k-th (1 \leq k \leq R) of the following R lines gives the pair of cities a_k, b_k specified in the k-th question, separated by a space.

Output

Output R lines. The k-th line (1 \leq k \leq R) should contain the answer to the k-th question. That is, if a_k \neq b_k, output the minimum durability value among all roads on the path connecting city a_k and city b_k; if a_k = b_k, output 0.

Sample Input 1

5
1 3
1 5
2 2
2 4
3
4 3
5 4
1 1
4
4 3
5 3
2 2
1 5

Sample Output 1

4
4
0
4

Sample Input 2

3
1 1000000000
1 0
2
2 3
1 1
3
2 3
1 2
3 3

Sample Output 2

1
1000000001
0

Sample Input 3

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

Sample Output 3

4
4
1
6
0
4
1

Sample Input 4

25
1 100
1 50
2 70
2 30
3 80
3 60
4 20
4 90
5 10
5 40
6 55
6 65
7 75
7 85
8 15
8 25
9 35
10 45
11 5
12 95
13 0
14 110
15 120
18 33
22
16 25
20 21
22 24
17 19
1 25
8 15
10 14
23 5
12 12
2 18
3 20
21 24
16 17
25 22
11 13
4 7
19 24
1 1
18 20
6 25
14 22
9 23
18
16 24
20 22
1 25
12 23
17 17
2 15
19 21
25 24
8 18
10 11
3 22
5 23
6 14
7 21
11 25
1 1
4 20
13 24

Sample Output 4

17
3
37
57
0
61
13
37
23
13
3
38
69
57
37
0
8
69

Sample Input 5

1
1
1 1
1
1 1

Sample Output 5

0