401933: GYM100589 A Queries on the Tree

You are given a directed tree with N with nodes numbered 1 to N and rooted at node 1. Each node initially contains 0 coins.

You have to handle a total of M operations:

• 1 L Y : Increase by Y the coins of all nodes which are at a distance L from root.
• 2 X : Report the sum of coins of all nodes in subtree rooted at node X.

First line contains N and M. Each of the next N - 1 lines contains u and v denoting directed edge from node numbered u to v.

Each of the next M lines contain queries of either Type 1 or 2.

For each query of Type 2, print the required sum.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁴
• 0 ≤ L ≤ Maximum height of tree
• 0 ≤ Y ≤ 10⁹
• 1 ≤ X, u, v ≤ N

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

8
10

In first update nodes 2 and 3 are increased by 2 coins each.

In second update nodes 4 and 5 are increased by 3 each.