AT_joisp2025_k 移住計画 (Migration Plan)

JOI 国有 $N$ 个城市，这些城市编号为 $1$ 到 $N$。在这些城市之间，有 $N-1$ 条**单向**道路。具体地，对于每个 $i = 2, 3, \ldots, N$，从城市 $i$ 到城市 $P_i$ 有一条道路。这里保证 $1 \leq P_i < i$。 每个城市都有一个**危险度**。作为首都的城市 $1$ 的危险度为 $0$。对于城市 $i$（$2 \leq i \leq N$），其危险度被定义为从城市 $i$ 通往城市 $1$ 的路径上经过的道路数。由于 JOI 国的结构，从城市 $i$ 到城市 $1$ 的路径恰好只有 $1$ 条。 现有 $K_i$ 只海狸分别住在城市 $i$（$1 \leq i \leq N$）。JOI 国总统 Bitarou 制定了海狸们的迁移计划。迁移计划将在接下来的 $Q$ 天内执行。第 $j$ 天（$1 \leq j \leq Q$），会发生以下 $3$ 种事件之一： - **迁移** 此时所有居住在危险度为 $X_j$ 的城市的海狸，会各自通过若干道路，前往它们从当前城市能通过道路到达的危险度为 $Y_j$ 的城市进行迁移。这里保证 $0 \leq Y_j < X_j$。由于 JOI 国的结构，对于每只海狸来说，目标迁移城市是唯一确定的。 - **接纳移民** 由于接纳了国外移民，居住在城市 $A_j$ 的海狸数量增加 $L_j$。 - **调查** 调查当前居住在城市 $B_j$ 的海狸数量。 作为 Bitarou 的下属，你发现你可以仅通过迁移计划的信息计算每次调查事件的结果，无需实际访问那些城市。 给定 JOI 国的结构、当前海狸的分布以及迁移计划的信息，请编写程序，计算每次调查事件的结果。

输入以以下格式从标准输入给出： > $N$ $P_2$ $P_3$ $\cdots$ $P_N$ > $K_1$ $K_2$ $\cdots$ $K_N$ > $Q$ > （第 $1$ 个查询） > （第 $2$ 个查询） > $\vdots$ > （第 $Q$ 个查询） 每一个查询（$1 \leq j \leq Q$）为一行若干空格分隔的整数。第一个整数为 $T_j$，其含义如下： - 当 $T_j = 1$ 时，接下来有两个整数 $X_j, Y_j$。表示第 $j$ 天发生的是迁移事件。那一天所有居住在危险度为 $X_j$ 的城市的海狸，会迁移到危险度为 $Y_j$ 的城市。 - 当 $T_j = 2$ 时，接下来有两个整数 $A_j, L_j$。表示第 $j$ 天发生的是接纳移民事件，城市 $A_j$ 的海狸增加 $L_j$。 - 当 $T_j = 3$ 时，接下来有一个整数 $B_j$。表示第 $j$ 天发生的是调查事件，需要输出当前城市 $B_j$ 的海狸数量。

对于每一个 $T_j = 3$ 的查询，依次输出调查城市的海狸数量，每个占一行。

## 小题目 令城市的最大危险度为 $D$。 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$），且 $T_j = 3$ 的 $j$ 的个数不超过 $5$。 5. （15 分）$T_j = 3$ 的 $j$ 的个数不超过 $5$。 6. （27 分）$T_j \neq 2$（$1 \leq j \leq Q$）。 7. （18 分）无额外限制。 --- ### 样例解释 1 最开始，城市 $1,2,3,4$ 分别有 $1,3,4,3$ 只海狸。各城市的危险度分别为 $0,1,1,2$。 - 第 $1$ 天发生调查事件。需输出城市 $1$ 的海狸数量，即 $1$。 - 第 $2$ 天发生迁移事件。所有居住在危险度 $1$ 的城市（即城市 $2,3$）的海狸全部转移到危险度 $0$ 的城市（城市 $1$）。此时城市 $1,2,3,4$ 的海狸数量变为 $8,0,0,3$。 - 第 $3$ 天发生调查事件。需输出城市 $1$ 的海狸数量，即 $8$。 - 第 $4$ 天发生调查事件。需输出城市 $2$ 的海狸数量，即 $0$。 - 第 $5$ 天发生迁移事件。所有危险度为 $2$ 的城市（即城市 $4$）的海狸迁移到危险度为 $1$ 的城市（城市 $2$）。此时城市 $1,2,3,4$ 的海狸数量为 $8,3,0,0$。 - 第 $6$ 天发生调查事件。需输出城市 $2$ 的海狸数量，即 $3$。 此输入数据满足小题目 $2,3,4,5,6,7$ 的限制。 --- ### 样例解释 2 最开始，城市 $1,2,3$ 分别有 $3,1,4$ 只海狸。各城市的危险度分别为 $0,1,1$。 - 第 $1$ 天发生接纳移民事件。城市 $2$ 的海狸增加 $5$。此时城市 $1,2,3$ 的海狸数量为 $3,6,4$。 - 第 $2$ 天发生迁移事件。危险度为 $2$ 的城市没有海狸，因此无人迁移。 - 第 $3$ 天发生调查事件。需输出城市 $1$ 的海狸数量，即 $3$。 - 第 $4$ 天发生迁移事件。所有危险度为 $1$ 的城市（城市 $2,3$）的海狸迁移到危险度为 $0$ 的城市（城市 $1$）。此时城市 $1,2,3$ 的海狸数量为 $13,0,0$。 - 第 $5$ 天发生调查事件。需输出城市 $1$ 的海狸数量，即 $13$。 - 第 $6$ 天发生调查事件。需输出城市 $2$ 的海狸数量，即 $0$。 - 后面事件同理，省略。 此输入数据满足小题目 $1,2,3,7$ 的限制。 --- ### 样例解释 3 此输入数据满足小题目 $2,3,5,7$ 的限制。 ### 约束条件 - $2 \leq N \leq 2\,000\,000$。 - $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 2\,000\,000$。 - $T_j$ 取 $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$ 的 $j$ 至少有一个。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译