Dragon Protection Squad Problem

You are given a tree with n sectors (nodes) numbered from 1 to n. Each sector has an initial protection level. The reporting structure of the Dragon Protection Squad forms a tree, where an edge between sectors u and v indicates a direct reporting relationship. The tree is rooted at sector 1. Define the subtree sum for a sector as:

\( S(u) = p[u] + \sum_{v \in \text{children}(u)} S(v) \)

Your task is to process queries of two types:

• 1 s x: Update the protection level of sector s to x.
• 2 s: Query and output the total protection level in the subtree of sector s (including itself).

Make sure your solution reads input from stdin and writes output to stdout.

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10⁵), the number of sectors. The next line contains n space-separated integers representing the initial protection levels of the sectors.

Then follow n-1 lines, each containing two space-separated integers u and v, indicating an undirected edge (reporting relationship) between sector u and sector v. It is guaranteed that these edges form a tree with root at sector 1.

The next line contains an integer q (number of queries). Each of the following q lines represents a query in one of the following formats:

• 1 s x — update the protection level of sector s to x.
• 2 s — query the sum of protection levels in the subtree of sector s.

outputFormat

For each query of type 2, output a single line containing the total protection level in the subtree of the given sector.

## sample

5
5 3 8 6 2
1 2
2 3
2 4
1 5
2
2 1
2 2

24
17

</p>