401933: GYM100589 A Queries on the Tree

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Queries on the Treetime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.
Input

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.

Output

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

Constraints

  • 1 ≤ N105
  • 1 ≤ M104
  • 0 ≤ L ≤ Maximum height of tree
  • 0 ≤ Y109
  • 1 ≤ X, u, vN
ExamplesInput
5 4
1 2
1 3
3 4
3 5
1 1 2
1 2 3
2 3
2 1
Output
8
10
Note

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.

加入题单

上一题 下一题 算法标签: