Subtree Updates and Queries

You are given a tree with n nodes numbered from 1 to n. The tree is rooted at node 1. Initially, every node has a value of 0. You need to process Q queries on the tree. There are two types of queries:

• Type 1: 1 u x — Add an integer x to all nodes in the subtree rooted at node u.
• Type 2: 2 u — Output the sum of the values in the subtree rooted at node u.

For a node u, its subtree consists of u and all nodes that are descendants of u in the tree. It is guaranteed that the given edges generate a tree. If a query requires you to update or compute sums over a subtree, you should perform the operations using a depth-first search (DFS) approach.

In mathematical notation, if we denote by \( val[i] \) the value of node \( i \), and if a query 1 u x is given, then for every node \( i \) in the subtree of \( u \), update:

\[ val[i] := val[i] + x \]

For a query 2 u, output:

\[ \sum_{i \in subtree(u)} val[i] \]

You are required to read from stdin and write to stdout.

inputFormat

The input is given as follows:

1. The first line contains two integers n and Q — the number of nodes and the number of queries.
2. The next n - 1 lines each contain two integers u and v indicating that there is an edge between nodes u and v.
3. The following Q lines each describe a query. A query is of the form 1 u x or 2 u as described above.

outputFormat

For each query of type 2, output the sum of the values in the subtree rooted at the given node on a separate line.

## sample

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

30
45
15

</p>