根号专题-你说的操作首先是什么在哪里操作

根号专题-你说的操作首先是什么在哪里操作

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给出一个\(n\)个节点的树,其中\(1\)号节点为根,所有边长度为\(1\),初始所有节点权值为\(0\)。
请支持如下两种操作:
\(1\) \(d\) \(x\),表示将所有深度为\(d\)的节点权值加上\(x\),深度定义为其到\(1\)号点最短路的长度。
\(2\) \(a\),表示查询以\(a\)为根的子树的点权和。
数据结构选手,给我上。

Format

Input

每个测试点仅包含一组输入数据。
第一行两个整数\(n,m(1<=n,m<=10^5)\),表示树的节点数和操作总数。
接下来\(n-1\)行,每行两个整数\(u,v(1<=u,v<=n)\),表示在节点\(u\)和节点\(v\)之间有一条边。
接下来\(m\)行,每行是如下两种形式之一:
\(1\) \(d\) \(x(0<=d<n,|x|<=10^8)\),表示进行第一类操作。
\(2\) \(a(1<=a<=n)\),表示进行第二类操作,你需要输出答案。
保证输入数据为一棵树。

Output

按照输入顺序,对于每个询问,输出一行一个整数表示答案。

Sample 1

Input

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

Output

2
6

Limitation

1s, 1GB for each test case.

Source

Vijos Original

根号大狂欢

未参加
状态
已结束
规则
ACM/ICPC
题目
2
开始于
2019-08-02 14:00
结束于
2019-08-02 17:00
持续时间
3.0 小时
主持人
参赛人数
28