← 返回题目列表

AtCoder · awc0100_j

J. 路网发展

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥负责管理由以下部分组成的道路网: N 城市。

该网络具有有根树的结构,其中包含城市 1 是大写字母(根)。每个城市 i (2 \leq i \leq N) 有指定的父城市 P_i (P_i < i),并且恰好存在一条直接连接城市的道路 i 及其母城市 P_i。我们将这条路称为 路 i。道路 i 有一个 耐久值 代表其对流量负载的抵抗力,初始耐久性值为 W_i。有 N - 1 道路总数,并且由于该结构是一棵树,因此连接任何两个城市的路径(不两次经过同一城市的道路序列)是唯一确定的。

高桥表演 Q 道路加固作业。在 j-th (1 \leq j \leq Q) 加固操作,他指定了两个城市 u_j, v_j 并增加连接城市的路径上每条道路的耐久性值 u_j 和城市 v_j by 1。如果 u_j = v_j,路径上没有道路,因此没有任何变化。同一条道路可以进行多次加固操作,每次其耐久性值都会增加 1.

毕竟 Q 增援行动已完成,青木询问 R 有关道路网络状况的问题。在 k-th (1 \leq k \leq R) 问题,他指定了两个城市 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
  • 第一行给出城市数量 N.
  • 以下 N - 1 行给出与城市对应的信息 2, 3, \ldots, N 按顺序。对应城市的线路 i (2 \leq i \leq N) 给出父城市 P_i 和初始耐久值 W_i 的道路 i (连接城市的道路 i 及其母城市 P_i),用空格分隔。
  • 下一行给出了加固操作的数量 Q.
  • 的 j-th (1 \leq j \leq Q) 以下内容 Q 行给出了一对城市 u_j, v_j 中指定 j第 次加固操作,以空格分隔。
  • 下一行给出问题数量 R.
  • 的 k-th (1 \leq k \leq R) 以下内容 R 行给出了一对城市 a_k, b_k 中指定 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