34113번 - Migration Plan 서브태스크다국어

JOI Kingdom consists of $N$ cities numbered from $1$ to $N$. There are $N − 1$ one-way roads connecting these cities. Specifically, for each $i = 2, 3, \dots , N$, there is a road leading from city $i$ to city $P_i$. Here, it is guaranteed that $1 ≤ P_i < i$.

Each of the $N$ cities has a defined danger level. The capital city, city $1$, has a danger level of $0$. For city $i$ ($2 ≤ i ≤ N$), the danger level is defined as the number of roads traversed in the path from city $i$ to city $1$. Due to the structure of JOI Kingdom, there is exactly one unique path from any city $i$ to city $1$.

Currently, there are $K_i$ beavers living in city $i$ ($1 ≤ i ≤ N$). The president of JOI Kingdom, Bitaro, has planned a beaver relocation program. This relocation plan will be executed over $Q$ days. On the $j$-th day ($1 ≤ j ≤ Q$), one of the following three types of events will occur:

• Relocation: All beavers living in a city with danger level $X_j$ at that moment will move to a city with danger level $Y_j$, which they can reach by traveling along one or more roads from their current city. It is guaranteed that $0 ≤ Y_j < X_j$. Due to the structure of JOI Kingdom, the relocation destination for each beaver is uniquely determined.
• Immigration: The number of beavers living in city $A_j$ increases by $L_j$ due to immigration from outside JOI Kingdom.
• Survey: The number of beavers currently living in city $B_j$ is surveyed.

As Bitaro’s subordinate, you realize that you can compute the number of beavers in each survey event based solely on the relocation plan’s information, without physically visiting the city.

Given the structure of JOI Kingdom, the current number of beavers living in each city, and the details of the relocation plan, write a program to compute the results of each survey event.

Read the following data from the standard input.

$N$

$P_2$ $P_3$ $\cdots$ $P_N$

$K_1$ $K_2$ $\cdots$ $K_N$

$Q$

(Query $1$)

(Query $2$)

$\vdots$

(Query $Q$)

Each (Query $j$) ($1 ≤ j ≤ Q$) consists of several integers separated by spaces. Let the first integer be $T_j$, then the content of this line is as follows:

• If $T_j = 1$, the line continues with two integers $X_j$, $Y_j$ in this order. This indicates that on day $j$, a relocation event occurs, where all beavers living in a city with danger level $X_j$ move to a city with danger level $Y_j$ that they can reach by traveling along one or more roads from their current city.
• If $T_j = 2$, the line continues with two integers $A_j$, $L_j$ in this order. This indicates that on day $j$, an immigration event occurs, increasing the number of beavers in city $A_j$ by $L_j$.
• If $T_j = 3$, the line continues with one integer $B_j$. This indicates that on day $j$, a survey event occurs, where the number of beavers currently living in city $B_j$ is surveyed.

For each $j$ ($1 ≤ j ≤ Q$) where $T_j = 3$, output the number of beavers in city $B_j$ at that moment, one per line, in order.

• $2 ≤ N ≤ 2\, 000\, 000$.
• $1 ≤ P_i < i$ ($2 ≤ i ≤ N$).
• $0 ≤ K_i ≤ 100$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 2\, 000\, 000$.
• $T_j$ is either $1$, $2$, or $3$ ($1 ≤ j ≤ Q$).
• If $T_j = 1$, then $0 ≤ Y_j < X_j ≤ N − 1$ ($1 ≤ j ≤ Q$).
• If $T_j = 2$, then $1 ≤ A_j ≤ N$, $1 ≤ L_j ≤ 100$ ($1 ≤ j ≤ Q$).
• If $T_j = 3$, then $1 ≤ B_j ≤ N$ ($1 ≤ j ≤ Q$).
• At least one $j$ ($1 ≤ j ≤ Q$) satisfies $T_j = 3$.
• All input values are integers.