Background

 子供の頃の夢は
 The dreams of childhood.
 色褪せない落書きで
 Are doodles that never fade.
 いつまでも描き続けられた
 Drawn again and again, forever.
 願う未来へとつながる
 Connected tightly to the future we wish for.
 鐘が鳴る音
 The sound of bells ringing.
 遠くから聞こえてくる
 Can be heard even from far away.
 素直な心に
 Reaching an honest heart.
 届いては響いてる
 And then echoing.
 光りは
 Turning into seven-colored.
 七色に変わって
 Light.

Problem Description

You are given a tree with $n$ nodes, and each node has a weight $v_i$.

In this statement, “DSU on tree merging” means: recursively merge sets from bottom to top. Each time, use the sum of node weights in a set as the key, and insert all nodes from the set with the smaller weight sum into the set with the larger weight sum. Initially, each node forms a set containing only itself.

Also, we fix the following enumeration order: assume all subtree merges have already been done recursively. When merging the current node’s level, start from the subtree root, sort its children in increasing order of their indices, and merge sets pairwise each time to obtain the set of the subtree.

Additionally, if two sets have the same weight sum, compare by the minimum node depth inside the set as the second key (merge the one with larger minimum depth into the one with smaller minimum depth).

The root of the tree is fixed to be $1$. You need to process the following query and update operations:

1 x means: query the weights of the nodes in the subtree rooted at $x$ that, after performing DSU on tree merging, have never been involved in an operation of “merging into another set”.

2 x d means: add $d$ to the weight of node $x$.

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$ is the initial weight of node $i$.

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

Then follow $q$ lines, each in the form 1 x or 2 x d, corresponding to the two operations described above.

Output Format

For each operation of type $1$, output one line with 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

Idea: FutaRimeWoawaSete, Solution: zhoukangyang, Code: Rainybunny, Data: FutaRimeWoawaSete/Rainybunny.

Constraints: for $100\%$ of the testdata, $1\le n,q\le2\times10^5$, $1\le p_i<i$; in operations, $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}$.

Translated by ChatGPT 5