AdditionalFile5054.zip

#5054. 「JOISC 2025 Day4」迁移计划

标签: 传统 | 时间限制: 7500 ms | 内存限制: 2048 MiB |

题目描述

题目译自 JOISC 2025 Day4 T2 「移住計画 / Migration Plan」

JOI 国有 $N$ 座城市，编号从 $1$ 到 $N$，通过 $N-1$ 条单向道路连接。具体来说，对于每座城市 $i$ $(2 \leq i \leq N)$，有一条从 $i$ 到 $P_i$ 的路，且 $1 \leq P_i < i$。

每座城市有其危险度。首都 $1$ 的危险度为 $0$，而城市 $i$ $(2 \leq i \leq N)$ 的危险度定义为从 $i$ 到 $1$ 的路径上道路数。JOI 国的结构保证每座城市到 $1$ 的路径唯一。

目前，城市 $i$ $(1 \leq i \leq N)$ 居住着 $K_i$ 只海狸。JOI 国总统比太郎制定了一项为期 $Q$ 天的移居计划，每天发生以下三种事件之一：

1. 移居：危险度为 $X_j$ 的城市中的所有海狸，移居到通过若干道路可达的危险度为 $Y_j$ $(0 \leq Y_j < X_j)$ 的城市，移居目标因结构唯一。
2. 接纳移民：城市 $A_j$ 的海狸数增加 $L_j$ 只，因 JOI 国外部移民到来。
3. 调查：统计当时城市 $B_j$ 的海狸数量。

作为比太郎的助手，你发现无需实地走访，仅凭移居计划信息就能计算每次调查的结果。

给定 JOI 国结构、初始海狸数和移居计划，编写程序计算每次调查的答案。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N-1$ 个整数 $P_2,P_3,\ldots ,P_N$。

第三行包含用空格分隔的 $N$ 个整数 $K_1,K_2, \ldots ,K_N$。

第四行包含一个整数 $Q$。

接下来 $Q$ 行，每行描述了一个事件，包含若干空格分隔的整数。令第一个数为 $T_j$，格式如下：

• $T_j = 1$：后接 $X_j, Y_j$，表示移居事件，危险度 $X_j$ 的海狸移至危险度 $Y_j$。
• $T_j = 2$：后接 $A_j, L_j$，表示接纳移民，城市 $A_j$ 增加 $L_j$ 只海狸。
• $T_j = 3$：后接 $B_j$，表示调查事件，查询城市 $B_j$ 的海狸数。

输出格式

对于每个 $T_j = 3$ $(1 \leq j \leq Q)$ 的调查事件，按顺序输出一行，表示当时城市 $B_j$ 的海狸数。

样例 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
8
0
3

最初，城市 $1, 2, 3, 4$ 分别居住着 $1, 3, 4, 3$ 只海狸。各城市的危险度分别为 $0, 1, 1, 2$。

第 $1$ 天是调查事件。因此，第一行输出此时城市 $1$ 的海狸数量，即 $1$。

第 $2$ 天是移居事件。此时，城市 $2$ 的海狸全部移居到城市 $1$。同时，城市 $3$ 的海狸也全部移居到城市 $1$。第 $2$ 天结束后，城市 $1, 2, 3, 4$ 分别居住着 $8, 0, 0, 3$ 只海狸。

第 $3$ 天是调查事件。因此，第二行输出此时城市 $1$ 的海狸数量，即 $8$。

第 $4$ 天是调查事件。因此，第三行输出此时城市 $2$ 的海狸数量，即 $0$。

第 $5$ 天是移居事件。此时，城市 $3$ 的海狸全部移居到城市 $2$。第 $5$ 天结束后，城市 $1, 2, 3, 4$ 分别居住着 $8, 3, 0, 0$ 只海狸。

第 $6$ 天是调查事件。因此，第四行输出此时城市 $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

输出

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$ 的海狸数量，即 $3$。

第 $4$ 天是移居事件。此时，城市 $2$ 的海狸全部移居到城市 $1$。同时，城市 $3$ 的海狸也全部移居到城市 $1$。第 $4$ 天结束后，城市 $1, 2, 3$ 分别居住着 $13, 0, 0$ 只海狸。

第 $5$ 天是调查事件。因此，第二行输出此时城市 $1$ 的海狸数量，即 $13$。

第 $6$ 天是调查事件。因此，第三行输出此时城市 $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

输出

6
18
19
6
0

这个样例满足子任务 $2,3,5,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 2000000$
• $1 \leq P_i < i \, (2 \leq i \leq N)$
• $0 \leq K_i \leq 100 \, (1 \leq i \leq N)$
• $1 \leq Q \leq 2000000$
• $T_j \in \{1, 2, 3\} \, (1 \leq j \leq Q)$
• $T_j = 1$ 时，$0 \leq Y_j < X_j \leq N-1 \, (1 \leq j \leq Q)$
• $T_j = 2$ 时，$1 \leq A_j \leq N, 1 \leq L_j \leq 100 \, (1 \leq j \leq Q)$
• $T_j = 3$ 时，$1 \leq B_j \leq N \, (1 \leq j \leq Q)$
• 至少存在一个 $T_j = 3$
• 所有输入为整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$4$	$D = 1$
$2$	$8$	$N \leq 20$
$3$	$13$	$D \leq 20$
$4$	$15$	$T_j \neq 2 \, (1 \leq j \leq Q)$，调查次数 $\leq 5$
$5$	$15$	调查次数 $\leq 5$
$6$	$27$	$T_j \neq 2 \, (1 \leq j \leq Q)$
$7$	$18$	无附加限制