Tree Operations with Subtree Sum Queries

You are given a tree with n nodes numbered from 1 to n. Each node has an integer value. The tree is rooted at node 1. You will be provided with the initial values of the nodes, followed by n-1 edges defining the tree structure, and then a number of queries.

There are two types of queries:

• Type 1: Update the value at a node. The query is given as: \(1\ x\ y\) which means update the value at node \(x\) to \(y\).
• Type 2: Report the sum of the subtree rooted at a node. The query is given as: \(2\ x\). The subtree of node \(x\) includes node \(x\) itself and all its descendants in the tree.

Your task is to perform these operations efficiently and output the answer for every type 2 query.

inputFormat

The first line contains an integer \(n\) \( (1 \leq n \leq 10^5)\) representing the number of nodes in the tree.

The second line contains \(n\) space-separated integers representing the initial values for nodes \(1, 2, \ldots, n\).

The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating that there is an edge connecting nodes \(u\) and \(v\).

The following line contains an integer \(q\) representing the number of queries.

The next \(q\) lines represent the queries. Each query is in one of the following formats:

• \(2\ x\) for a subtree sum query.
• \(1\ x\ y\) for an update query (set the value of node \(x\) to \(y\)).

outputFormat

For each query of type 2, output the sum of the subtree rooted at the given node. Each result should be printed on a new line.

## sample

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

15
24

</p>