Tree Subtree Sum Queries

You are given a tree with (n) nodes (indexed from 1 to (n)) and rooted at node 1. Initially, each node has a value of 0. You will be provided with a series of operations to update the tree and answer queries. There are two types of operations:

1. add i x: Increase the value at node (i) by (x).
2. query i: Output the sum of the values in the subtree of node (i) (including node (i) itself).

The tree structure is fixed, and after each add operation, the changes affect subsequent query operations. The subtree of a node is defined as that node and all its descendants in the tree.

The DFS algorithm (in (O(n))) is used to compute subtree sums when a query is made following the modifications. Make sure your solution resets any cached subtree computations upon an update.

Note: The input is provided via standard input and the output should be written to standard output. All numeric values and operations are space-separated.

inputFormat

The first line contains two integers (n) and (m), where (n) is the number of nodes in the tree and (m) is the number of operations. The next (n-1) lines each contain two integers (u) and (v), denoting an edge between nodes (u) and (v). The following (m) lines each describe an operation in one of the following formats:

• add i x
• query i

Each operation is provided on a separate line.

outputFormat

For each query operation, output the sum of the values in the corresponding subtree on a new line.## sample

5 5
1 2
1 3
1 4
4 5
add 2 10
add 4 5
query 1
query 4
query 5

15
5
0