You are given a tree of N nodes. The nodes are numbered from 1 to N. The tree is rooted at node numbered 1.
There is a cost associated with each node. Initially the cost is equal to the number of the node.
eg. The node numbered 1 has initial cost 1, node numbered 5 has initial cost 5.
There are 2 types of operations that can be performed on the tree.
Type 1 :
Format - 1 U X
Operation - You are given two integers U and X. Add X to the cost of each node in the subtree of U.
Type 2 :
Format - 2 U
Operation - You are given one integer U. Print the sum of cost of nodes that come in the path from 1 to U (including 1 and U).
Input
- The first line contains two integers N and Q, the number of nodes and the number of operations.
- The next N - 1 lines contains two integers U and V. There is an edge between U and V.
- The next Q lines contain one operation per line.
Output
For each operation of type 2, print the answer to the operation.
Constraints
- 1 ≤ N, Q, U, V, X ≤ 100000
Initially, cost[1] = 1, cost[2] = 2, cost[3] = 3, cost[4] = 4, cost[5] = 5.
After first operation the cost[1] = 2, cost[2] = 3, cost[3] = 4, cost[4] = 5, cost[5] = 6.
For second operation sum of cost of nodes in the path from 1 to 5 = cost[1] + cost[2] + cost[5] = 11
After third operation the cost[1] = 2, cost[2] = 6, cost[3] = 4, cost[5] = 8, cost[5] = 9.
For fourth operation the sum of cost of nodes in the path from 1 to 4 = cost[1] + cost[2] + cost[4] = 16
For fourth operation the sum of cost of nodes in the path from 1 to 3 = cost[1] + cost[3] = 6
