← 返回题目列表

AtCoder · joisp2025_k

K. 迁移计划

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

配点: 100 点

在JOI国有 N 个城镇,每个城镇有 它们的编号最大为 1 它们的编号最大为 N 。 连接这些城市 N-1 书 有一条路名为 一方通行 。 具体来说,每个 i = 2, 3, \ldots, N 关于城市 i 从城镇出发 有一条路通向 P_i 。 在这里,1 \leqq P_i < i 有保证。

N 每个城镇都有 危険度 已定义。 首都的城市 1 的危险等级是 0 。 城市 i (2\leqq i \leqq N) 的危险等级为 它被定义为到 i 从城镇出发 有一条路通向 1 的路线上行驶的道路数量。 这里,由于JOI国家的结构, 到 i 从城镇出发 有一条路通向 1 的路线只是 1 请注意,有两个。

現在街 i (1\leqq i \leqq N) 中有 K_i 海狸住在那里。 JOI国家的总统比塔罗为河狸制定了迁徙计划。 移民计划现在开始 它运行 Q 天。 j 日目 (1\leqq j \leqq Q)具有以下内容 3 任何类型 1 发生了两个事件。

  • 移住
    此时的风险级别 居住在 X_j 镇的所有海狸从各自居住的镇经过几条道路即可到达的危险程度。 搬到 Y_j 市。在这里,0\leqq Y_j < X_j 有保证。请注意,由于 JOI 国家的结构,每只海狸的迁徙目的地都是唯一确定的。

  • 移民受理
    JOI 通过接受来自国外的移民,该市 居住在 A_j 的海狸数量 增加 L_j 。

  • 調査
    那时城市 找出 B_j 中生活着多少只海狸。

作为 Bitaro 的下属,你发现你可以仅根据迁徙计划信息来计算海狸的数量,而无需在每次调查活动期间实际访问该城市。

JOI 编写一个程序,根据有关国家结构、当前居住在那里的海狸数量以及迁徙计划的信息,计算每个调查事件的结果。


入力

输入是按以下格式从标准输入给出的。

N
P_2 P_3 \cdots P_N
K_1 K_2 \cdots K_N
Q
(\text{Query }1)
(\text{Query }2)
\vdots
(\text{Query }Q)

各 (\text{Query }j) (1\leqq j \leqq Q) 包含多个以空格分隔的整数。这几天之一 1 第一个整数 T_j 该行的内容是以下内容之一。

  • T_j = 1 ,此行后面是2 整数 给出了 X_j, Y_j 按此顺序写入。这是 j 当日事件为迁移事件,风险等级为 代表搬到 X_j 镇的所有海狸从各自居住的镇经过几条道路即可到达的危险程度。 搬到 Y_j 市。
  • T_j = 2 ,此行后面是2 整数 给出了 A_j, L_j 按此顺序写入。这是 j 当天的活动是移民接纳活动,镇 它代表增加 A_j 的海狸数量 增加 L_j 。 写入
  • T_j = 3 ,此行后面是1 整数 给出了 B_j 。这是 j 当天的事件是调查事件,此时 代表调查居住在 B_j 的海狸数量。

出力

j 当天的活动是一个研究活动,即 T_j = 3 是 j (1 \leqq j \leqq Q) 对于每个事件,按顺序将调查事件的结果输出到标准输出。 1 逐行输出。

制約

  • 2 \leqq N \leqq 2\,000\,000.
  • 1 \leqq P_i < i (2 \leqq i \leqq N).
  • 0 \leqq K_i \leqq 100 (1 \leqq i \leqq N).
  • 1 \leqq Q \leqq 2\,000\,000.
  • T_j 是 1, 2, 3 ( 当1\leqq j \leqq Q).
  • T_j=1 时,0 \leqq Y_j < X_j \leqq N-1 (1\leqq j \leqq Q).
  • T_j=2 时,1\leqq A_j \leqq N,1 \leqq L_j \leqq 100 (1\leqq j \leqq Q).
  • T_j=3 时, 1 \leqq B_j \leqq N (1\leqq j \leqq Q).
  • T_j=3 变为 j (1\leqq j \leqq Q)是 1 不止一个。
  • 所有输入值都是整数。

小課題

城市最高危险等级 D 。

  1. (4 点) D = 1.
  2. (8 点) N \leqq 20.
  3. (13 点) D\leqq 20.
  4. (15 点) T_j\neq 2 (1\leqq j\leqq Q).此外,T_j = 3 变为 j (1\leqq j\leqq Q) 的数量是 分别为 5 以下.
  5. (15 点) T_j = 3 变为 j (1\leqq j\leqq Q) 的数量是 分别为 5 以下.
  6. (27 点) T_j\neq 2 (1\leqq j\leqq Q).
  7. (18 点)没有额外的限制。

入力例 1

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

出力例 1

1
8
0
3

最初,街 1,2,3,4 。 1,3,4,3 那里住着海狸。 此外,每个城市都有自己的危险程度。 0,1,1,2 。

1 当天将发生调查事件。 因此,1 该点所在城市在队列中 是居住在 1 的海狸数量 迁移事件发生在 1 。

2 天。 那时的城镇 2 住在城市里的海狸 移至 1 。 而且,那个时候,这座城市 住在 3 的海狸也是一座城市。 移至 1 。 2 归根结底,这座城市 1,2,3,4 。 8,0,0,3 那里住着海狸。 在

3 当天将发生调查事件。 因此,2 该点所在城市在队列中 是居住在 1 的海狸数量 迁移事件发生在 8 。

4 当天将发生调查事件。 因此,3 该点所在城市在队列中 是居住在 2 的海狸数量 迁移事件发生在 0 。

5 天。 那时的城镇 4 住在城市里的海狸 移至 2 。 5 归根结底,这座城市 1,2,3,4 。 8,3,0,0 那里住着海狸。 在

6 当天将发生调查事件。 因此,4 该点所在城市在队列中 是居住在 2 的海狸数量 迁移事件发生在 3 。

此输入示例是一个小作业。 2,3,4,5,6,7 满足约束。


入力例 2

3
1 1
3 1 4
11
2 2 5
1 2 0
3 1
1 1 0
3 1
3 2
2 3 4
3 3
1 1 0
3 3
3 1

出力例 2

3
13
0
4
0
17

最初,街 1,2,3 。 3,1,4 那里住着海狸。 此外,每个城市都有自己的危险程度。 0,1,1 。

1 日,将会发生移民接受事件。 城市 增加 2 的海狸数量 增加 5 。 迁移事件发生在 1 归根结底,这座城市 1,2,3 。 3,6,4 那里住着海狸。 在

2 天。 到时候,风险 2 市内没有海狸居住,因此不会发生迁徙。

3 当天将发生调查事件。 因此,1 该点所在城市在队列中 是居住在 1 的海狸数量 迁移事件发生在 3 。

4 天。 那时的城镇 2 住在城市里的海狸 移至 1 。 而且,那个时候,这座城市 住在 3 的海狸也是一座城市。 移至 1 。 4 归根结底,这座城市 1,2,3 。 13,0,0 那里住着海狸。 在

5 当天将发生调查事件。 因此,2 该点所在城市在队列中 是居住在 1 的海狸数量 迁移事件发生在 13 。

6 当天将发生调查事件。 因此,3 该点所在城市在队列中 是居住在 2 的海狸数量 迁移事件发生在 0 。

7 当天之后也会发生类似的事件,但此处省略说明。

此输入示例是一个小作业。 1,2,3,7 满足约束。


入力例 3

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

出力例 3

6
18
19
6
0

此输入示例是一个小作业。 2,3,5,7 满足约束。