Tree Query Operations

Given a tree with (N) nodes numbered from 1 to (N), each node has an initial integer value. The tree is rooted at node 1. You are provided with (N-1) edges that describe the tree structure. Your task is to process (Q) queries on this tree. There are three types of queries:

1. (\texttt{SUM x}): Output the sum of the values in the subtree of node (x). The subtree of node (x) includes node (x) and all of its descendants (when the tree is rooted at 1).

2. (\texttt{ADD x y}): Increase the value of node (x) by (y).

3. (\texttt{SET x y}): Set the value of node (x) to (y).

After every update query ((ADD) or (SET)), the changes are applied immediately and affect subsequent queries. Use depth-first search (DFS) to compute subtree sums after each update.

inputFormat

The input is provided via standard input (stdin) with the following format:

• The first line contains an integer (N), the number of nodes.
• The second line contains (N) space-separated integers indicating the initial values of the nodes.
• The next (N-1) lines each contain two integers (u) and (v), representing an edge between nodes (u) and (v).
• The following line contains an integer (Q), the number of queries.
• The next (Q) lines each contain a query in one of the following formats:
  • "SUM x"
  • "ADD x y"
  • "SET x y"

outputFormat

For each query of type "SUM", output the computed sum on a separate line via standard output (stdout).## sample

5
1 2 3 4 5
1 2
1 3
3 4
3 5
3
SUM 3
ADD 3 2
SUM 3

12
14