Tree Data Storage System

You are given a tree with n nodes. Initially, each node has a value of 0.

You need to perform q operations on the tree. There are two types of operations:

• Type 1: 1 u d — Add an integer d to the value at node u.
• Type 2: 2 u — Query the sum of values in the subtree rooted at node u.

The tree is given in an unrooted form with n-1 edges. You must first convert the tree into a rooted tree with node 1 as the root, and then process the queries as they come.

Note: When answering a query of type 2, compute the sum using a depth-first search (DFS) over the subtree and output the result on a new line.

The mathematical formulation for the subtree sum on a node u is given by:

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

where \(\text{value}[u]\) is the current value stored at node \(u\), and \(\text{children}(u)\) is the set of nodes that are direct children of \(u\) in the rooted tree.

inputFormat

The first line contains two integers n and q — the number of nodes and the number of queries respectively.

The next n-1 lines each contain two integers u and v representing an edge between nodes u and v.

The following q lines describe the operations. Each line begins with an integer representing the type of the operation:

• If the type is 1, it is followed by two integers u and d, meaning add d to the value at node u.
• If the type is 2, it is followed by an integer u, meaning output the sum of values in the subtree rooted at node u.

outputFormat

For each query of type 2, output a single line containing the sum of values within the specified subtree.

## sample

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

5
15
10

</p>