分数: 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