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.

서브태스크

힌트