← 返回题目列表

Codeforces · 276/E

E. 小女孩和树上的问题

中文机器翻译题面 查看原题

一个小女孩非常喜欢树上的问题。这是其中之一。

树是无向连通图,不包含环。树中节点 x 的度是树的节点 y 的数量,使得每个节点都通过树的某些边与节点 x 连接。

让我们考虑一棵由 n 个节点组成的树。我们将考虑索引从 1 到 n 的树节点。所考虑的树具有以下性质:除了节点号1之外的每个节点的度至多为2。

最初,树的每个节点都包含数字 0。您的任务是快速处理两种类型的请求:

- 表格请求:0 v x d。为了响应该请求,您应该将 x 添加到写入距离节点 v 至多 d 的节点中的所有数字。两个节点之间的距离是它们之间最短路径上的边数。
- 表单请求:1 v。在回复请求时,您应该打印节点 v 中写入的当前编号。

输入

第一行包含整数 n (2 ≤ n ≤ 105) 和 q (1 ≤ q ≤ 105) — 相应地,树节点的数量和请求的数量。

接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi),这表明节点 ui 和 vi 之间存在一条边。每条边的描述在输入中只出现一次。保证给定的图是具有语句中描述的属性的树。

接下来 q 行描述请求。

- 添加请求具有以下格式:0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n)。
- 打印节点值的请求具有以下格式:1 v (1 ≤ v ≤ n)。

行中的数字由单个空格分隔。

输出

对于每个打印节点值的请求,打印一个整数 - 对请求的答复。

示例

输入 #1

3 6
1 2
1 3
0 3 1 2
0 2 3 1
0 1 5 2
1 1
1 2
1 3

输出 #1

9
9
6

输入 #2

6 11
1 2
2 5
5 4
1 6
1 3
0 3 1 3
0 3 4 5
0 2 1 4
0 1 5 5
0 4 6 2
1 1
1 2
1 3
1 4
1 5
1 6

输出 #2

11
17
11
16
17
11