Background

Problem Description

The Geo Archon gives you a rooted tree with root $1$. Each node has a weight $a_i$. You need to support the following operations:

• $\texttt{1 u}$: Query the maximum value in the subtree rooted at $u$.
• $\texttt{2 u}$: For every node in the subtree rooted at $u$, change its weight simultaneously to the sum of the weights of all its children. That is, perform $\forall x \in \operatorname{subtree}(u), a_x\gets \sum_{y\in \operatorname{son}(x)}a_y$. Here, simultaneously means: when updating a node, its children are considered to remain in the state before this operation is applied.

Input Format

The first line contains two positive integers $n, q$, representing the size of the tree and the number of queries.
The second line contains $n$ positive integers, where the $i$-th number is the initial weight $a_i$ of node $i$.
The third line contains $(n-1)$ integers, where the $i$-th integer $\mathit{fa}_{i+1}$ represents the parent index of node $(i+1)$.
Then follow $q$ lines, each containing two integers representing one operation. The specific format is given in the “Description”.

Output Format

For each $\texttt{1}$ operation, output one integer per line as the answer.

6 6
1 1 4 5 1 4
1 2 2 4 1
1 2
1 1
2 4
1 2
2 2
1 1

5
5
4
5

15 12
512902574 823918122 595349487 580400545 453562767 72015781 850655655 442513356 619194214 644523811 935104539 371670625 477236621 785497862 282980318 
1 2 2 1 2 6 2 2 4 9 6 4 12 1 
2 5
2 1
2 1
2 4
2 15
1 2
1 3
2 2
2 7
1 1
1 2
1 6

3279191251
0
2309473383
785497862
0

Hint

[Sample Explanation]

Before any modification, the weights of each node are $1,1,4,5,1,4$.
After the first modification, they become $1,1,4,1,0,4$.
After the second modification, they become $1,5,0,0,0,4$.

A more intuitive picture

[Constraints]

The input size of this problem is large, so please pay attention to constant-factor optimizations.

For $100\%$ of the data, $1\le n, q \le 10^6$, $1 \le u \le n$, $0 \le a_i \le 10^9$, and $\mathit{fa}_i < i$.

Below are the subtasks (a blank field means there is no special property). You must pass all test points in a subtask and all test points in the subtasks it depends on to get the score for that subtask:

Special properties:

• For test points with special property A, it is guaranteed that in every operation of type $1$, $u = 1$.
• For test points with special property B, it is guaranteed that in every operation of type $2$, $u = 1$.
• For test points with special property C, it is guaranteed that for all nodes $i$, $\mathit{fa}_i = i - 1$. In other words, the tree is a chain.
• For test points with special property D, it is guaranteed that for all nodes $i$, $\mathit{fa}_i = 1$. In other words, the tree is a star.
• For test points with special property E, it is guaranteed that the testdata is random. Here, random means that operations $\texttt{1}$ and $\texttt{2}$ appear with equal probability, $u$ is chosen uniformly at random from $[1, n]$, and $\mathit{fa}_i$ is chosen uniformly at random from $[1, i - 1]$.

Hint: Since the problem setter is very lazy and Luogu cannot upload too many test points, the testdata of this problem may be relatively weak. Also, to avoid longer running time due to heavy load on the contest judge machines, the time limit has been relaxed. Therefore, everyone is welcome to try passing this problem with strange hacky approaches.

May we cleanse the four directions, and guard a corner of the mortal world.

Translated by ChatGPT 5