Tree Subtree Query Update Problem

Given a tree with \(n\) nodes where each node has an associated value, you need to process a series of queries. The tree is rooted at node 1. There are two types of queries:

• Type 1: Given a node \(x\), output the sum of the values in the subtree rooted at \(x\).
• Type 2: Given a node \(x\) and a value \(y\), update the value at node \(x\) to \(y\) and then recalculate the subtree sums.

After processing each update query, the subtree sums must be recalculated. For each query of type 1, print the corresponding subtree sum on a new line.

inputFormat

The input is given in the following format:

• The first line contains two integers \(n\) and \(q\) — the number of nodes and the number of queries, respectively.
• The second line contains \(n\) integers representing the initial values of the nodes (1-indexed).
• The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge of the tree.
• The following \(q\) lines each contain a query in one of the following formats:
  • 1 x — output the sum of the subtree rooted at node \(x\).
  • 2 x y — update the value of node \(x\) to \(y\).

outputFormat

For each query of type 1, print the sum of the subtree rooted at the given node on a new line.

## sample

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

3
19

</p>