Tree Path Sum Queries

You are given a tree with N nodes numbered from 1 to N. The tree is rooted at node 1. Each node has an initial weight. You are then given M operations of three types:

• Operation 1: Increase the weight of a single node x by a.
• Operation 2: Increase the weight of every node in the subtree rooted at x by a.
• Operation 3: Query the sum of weights on the path from node x to the root (including both x and the root).

Note: Any formula must be formatted in LaTeX. For example, the number of nodes is given by \(N\) and the number of operations by \(M\). The subtree of node \(x\) consists of all nodes \(u\) such that the unique path from the root to \(u\) passes through \(x\).

Input Format:

• The first line contains two integers \(N\) and \(M\).
• The second line contains \(N\) integers: the initial weights of nodes \(1, 2, \dots, N\) respectively.
• The next \(N-1\) lines each contain two integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\). It is guaranteed that these edges form a tree with root 1.
• The following \(M\) lines describe the operations. An operation is described as follows:
  • If the operation is type 1 or type 2, the line contains three integers: type x a.
  • If the operation is type 3, the line contains two integers: type x.

Output Format:

• For each operation of type 3, output a single integer on a new line representing the sum of weights on the path from node \(x\) to the root after performing all previous operations.

inputFormat

The input is given in the following format:

N M
w1 w2 ... wN
u1 v1
u2 v2
... (N-1 lines)
[operation 1 details]
[operation 2 details]
... (M lines total)

Here, wi is the initial weight of node \(i\), and each operation is either a three-integer line (for type 1 and 2 operations) or a two-integer line (for type 3 operations).

outputFormat

For each query operation (type 3), output the answer on a new line.

sample

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

8
18
28