Chain Update and Query on a Weighted Tree

Little Ω has invented a data structure problem based on a weighted tree. You are given a tree with n nodes numbered from 1 to n. For every node i (where \(2 \le i \le n\)), its parent is \(f_i\) (with \(1 \le f_i < i\)). Each node i has an initial weight \(a_i\) provided by the input.

You need to support the following two types of operations on the tree:

• 0 x y v: Increase the weight of every node on the simple path from x to y by \(v\).
• 1 x y: Query the sum of weights of nodes on the simple path from x to y.

Note: The space limit for this problem is restricted to 64 MB.

The mathematical formulas in this problem are shown in \(\LaTeX\) format. For example, the condition for the parent is given as \(f_i \in [1,i-1]\), and the update/query operations involve paths and sums.

inputFormat

The first line contains two integers \(n\) and \(Q\) denoting the number of nodes in the tree and the number of operations, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the initial weight of the \(i\)-th node.

The third line contains \(n-1\) integers \(f_2, f_3, \dots, f_n\) where \(f_i\) is the parent of node \(i\) (with \(1 \le f_i < i\)).

Then, \(Q\) lines follow, each describing an operation in one of the following formats:

• 0 x y v: Increase the weights along the simple path from node \(x\) to node \(y\) by \(v\).
• 1 x y: Output the sum of weights along the simple path from node \(x\) to node \(y\).

outputFormat

For each operation of type 1 x y, output a single line containing the sum of weights on the simple path from \(x\) to \(y\).

sample

5 5
1 2 3 4 5
1 1 2 2
1 4 5
0 1 3 10
1 1 3
0 3 4 2
1 3 4

11
24
38