Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ or the problem author who authorized BZOJ to use it. If you are the copyright holder and believe that we have infringed your rights, please contact us.

Problem Description

A huge army of cg has discovered a city with extremely rich mineral resources, and they plan to carry out a new mining strategy in this city.

The city can be viewed as a rooted tree with $n$ nodes. We label each node with an integer from $1$ to $n$. For convenience, for any non-root node $v$, the label of any ancestor of $v$ is strictly smaller than $v$. Each node on the tree represents a mining site, and each edge represents a road.

As a squad leader in the cg army, you have $m$ subordinates. You have a 2D dynamic information table, where $T_{i,j}$ denotes the value in row $i$ and column $j$. When you are allowed to mine a certain region, you can assign your subordinates to mining sites. If you assign $j$ people to mining site $i$, you can obtain $T_{i,j}$ units of minerals.

A minable region is described as follows: you are given a pair of mining sites $(u,v)$, and it is guaranteed that $v$ is an ancestor of $u$ (here “ancestor” includes $u$ itself). The subtree rooted at $u$ is the controlled area, where you may freely assign subordinates to any nodes in this subtree. The simple path from $u$ to $v$ (excluding $u$ but including $v$; if $u=v$, then it includes $u$) is the exploration path, and on this path you may choose at most one mining site to assign subordinates to. The profit of this mining operation is the sum of the profits of all mining sites to which at least one subordinate is assigned.

Input Format

The first line contains $5$ positive integers $n,m,A,B,Q$. Here $n$ is the number of mining sites, and $m$ is the number of subordinates. $A,B,Q$ are values related to the dynamic information table.

The second line contains $n-1$ positive integers. The $i$-th integer is $F_{i+1}$, which indicates the parent of node $i+1$.

Next, you need to generate $n$ groups of data in order using the method described below. Each group contains $m$ numbers. For the $i$-th group, these $m$ numbers are the $m$ values in row $i$ of the information table. Immediately after that, one line contains a positive integer $C$, indicating the number of events.

Finally, $C$ lines follow, each describing an event. Each event starts with an integer $0$ or $1$.

• If it is $0$, then a positive integer $p$ follows, meaning the information table is updated. You need to generate a group of $m$ numbers to replace the $m$ values in row $p$ of the table.
• If it is $1$, then two positive integers $u,v$ follow, meaning a minable region appears, and you need to answer the profit of this mining operation.

All numbers on the same line are separated by exactly one space, with no extra spaces or newlines.

The data generation method is as follows: each time, generate a group of $m$ numbers in nondecreasing order to replace one row of the dynamic information table. The $j$-th smallest number replaces the value in column $j$ of that row. Call the following code $m$ times and sort the results to obtain one group of data. (Note that duplicate numbers may appear.)

Function GetInt 

A←((A xor B)+(B div X)+(B * X))and Y 
B←((A xor B)+(A div X)+(A * X))and Y 

return (A xor B)mod Q 

Here $A,B,Q$ are stored as 32-bit signed integers (C/C++ type signed long int, Pascal type longint). $X=2^{16}$, $Y=2^{31}-1$. xor is bitwise XOR, div is integer division, and is bitwise AND, and mod is modulo. Since only the lowest $31$ bits are kept, it is easy to see that we do not need to worry about overflow. Note that each call will modify both $A$ and $B$.

Output Format

For each mining event (an event starting with $1$), output one line with one integer, the profit for that operation.

10 5 1 2 10
1 1 3 3 4 4 6 6 9
4
1 6 3
1 9 1
0 1
1 1 1

11
9
12

Hint

Sample Explanation

The initial information table is:

After the change, row $1$ becomes:

1 1 1 4 7

In the first mining operation, you may assign subordinates freely among mining sites $6,8,9,10$, and you may choose one of mining sites $3$ or $4$ to assign subordinates. One optimal assignment is to assign $4$ people to mining site $6$ and $1$ person to mining site $8$. In the second mining operation, you may assign at mining site $9$, and you may choose one among mining sites $6,4,3,1$ to assign. One optimal assignment is to assign $1$ person to mining site $9$ and $4$ people to mining site $6$.

Constraints

There is $50\%$ of the testdata where, for every integer $i$ satisfying $2\leq i\leq n$, $F_i=i-1$. In this part, $40\%$ of the testdata (i.e. $20\%$ of all testdata) satisfies $n\leq 500$, $m\leq 20$, $C\leq 500$.

Besides the above, there is another $40\%$ of the testdata satisfying $n\leq 500$, $m\leq 20$, $C\leq 500$.

For $100\%$ of the testdata, $1\leq n\leq 20000$, $1\leq m\leq 50$, $1\leq C\leq 2000$. For every integer $i$ satisfying $2\leq i\leq n$, $1\leq F_i<i$. $1\leq A,B\leq 2^{31}-1$, $1\leq Q\leq 10000$.

Translated by ChatGPT 5