Background

"Long-growing warm winds blow at dawn, lotus leaves lightly open, and roses fall."

The last rehearsal performance at school!

From the first time on stage until now, from the empty playground after school as once agreed to today’s training room filled with sweat day and night, have their promises to each other changed?

"The guitar on our shoulders and our little dreams need to grow strong wings for them!"

Minor Heat "Can you hear me now? I will become your pride from now on. We are setting off right now. Everything is just right."

Background

Problem Description

Do you still remember? You are Tianyi and the others’ professional analyst. Besides the performers’ performance, the audience’s emotional fluctuations are also important targets for analysis. After unremitting effort, you proposed the following indicators (the setter has already been eliminated by you, but please still read patiently):

"Emotion" We use an intensity $v\in\mathbb N^\star$ to represent an emotion.

"Mood state" A series of emotions together form a mood state. We describe a mood state as an ordered pair $M=(s,f)$, where $s,f\in\mathbb N^\star$. Here, $s$ is the sum of the intensities of the emotions contained, and $f$ is the intensity of a certain characteristic emotion.

"Resonance" Two mood states can be fused into a new mood state through resonance. We denote the resonance that fuses $M_2=(s_2,f_2)$ into $M_1=(s_1,f_1)$ as $M_1+M_2$. The result of resonance is a new mood state $M=M_1+M_2=(s_1+s_2,f_1)$. Note that it is not necessarily true that $M_1+M_2=M_2+M_1$.

"Mood journey" On a rooted tree, the process of resonating mood states along the tree structure is called a mood journey. For the subtree rooted at $r$, its mood journey can be described as follows:

1. Initially, $A_r\gets M_r$, where $A_x$ denotes the final mood state after completing the mood journey of the subtree rooted at $x$, and $M_x$ is the initial mood state at node $x$.

2. Enumerate the children $x$ of $r$ in increasing order of node index:

   • Recursively complete the mood journey of the subtree of $x$, obtaining $A_x$. At this moment, let $A_r=(s_r,f_r)$ and $A_x=(s_x,f_x)$.

   • If $s_r\ge s_x$, set $A_r\gets A_r+A_x$; otherwise, set $A_r\gets A_x+A_r$.

The final $A_r$ is the final mood state after completing the mood journey of the subtree rooted at $r$.

To study the psychological changes of a specific audience member, you need to monitor the above indicators at all times. Now you are given a rooted tree with $n$ nodes, rooted at node $1$. At node $x$, the initial mood state is $M_x=(a_x,a_x)$. Then there are $q$ operations, and each operation is one of the following two types:

1. Given a node $x$, query the value of $f_x$ in $A_x=(s_x,f_x)$, where $A_x$ should be recomputed for each query according to the current information.

2. Given a node $x$ and a change amount $d$, set $a_x\gets a_x+d$, and modify the corresponding $M_x$. Note that $d$ may be negative, but it is guaranteed that $a_x>0$ both before and after the operation.

For each query operation, compute the corresponding answer.

Input Format

The first line contains two integers $n,q$, representing the size of the tree and the number of operations.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, where $a_i$ represents the initial weight of node $i$.

The third line contains $n-1$ integers $p_2,p_3,\cdots,p_n$, where $p_i$ represents the parent of node $i$ when the tree is rooted at node $1$.

The next $q$ lines each have the format 1 x or 2 x d, corresponding to the two types of operations described above.

Output Format

For each operation of type $1$, output one line containing one integer, representing the required answer.

5 10
2 10 1 10 3
1 2 3 2
2 1 3
1 3
1 5
2 3 5
2 3 2
1 5
2 5 6
1 3
2 5 -1
2 3 0

10
3
3
10

Hint

Constraints and Conventions

For $100\%$ of the testdata, $1\le n,q\le2\times10^5$, $1\le p_i<i$; the operations give $x\in[1,n]$, $d\in[-10^{18},10^{18}]$. At any time, $a_x\ge 1$ and $\sum_{x=1}^na_x\le10^{18}$.

For different subtasks, the following constraints apply:

• Special Property $\textbf A$: For $i\in[2,n]$, $p_i=i-1$.

• Special Property $\textbf B$: It is guaranteed that when rooted at $1$, the original tree is a binary tree. Also, for $i\in[2,n]$, there exists a tree path from $1$ to $i$ whose number of edges is at most $20$.

Translated by ChatGPT 5