配点: 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 。
- (4 点) D = 1.
- (8 点) N \leqq 20.
- (13 点) D\leqq 20.
- (15 点) T_j\neq 2 (1\leqq j\leqq Q).此外,T_j = 3 变为 j (1\leqq j\leqq Q) 的数量是 分别为 5 以下.
- (15 点) T_j = 3 变为 j (1\leqq j\leqq Q) 的数量是 分别为 5 以下.
- (27 点) T_j\neq 2 (1\leqq j\leqq Q).
- (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 满足约束。