AT_joisp2025_k.移住計画 (Migration Plan)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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$ 的查询，依次输出调查城市的海狸数量，每个占一行。

输入#1

输出#1

输入#2

输出#2

输入#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

小题目

令城市的最大危险度为 $D$ 。

最开始，城市 $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$ 的限制。

最开始，城市 $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$ 的限制。

此输入数据满足小题目 $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 翻译

输入解题思路，AI测评打分。不知道怎么写?