← 返回题目列表

Codeforces · 1076/E

E. 瓦夏和一棵树

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

Vasya 有一个由 $$$n$$$ 个顶点组成的树,根位于顶点 $$$1$$$。首先,所有顶点上都写有$$$0$$$。

令 $$$d(i, j)$$$ 为顶点 $$$i$$$ 和 $$$j$$$ 之间的距离,即从 $$$i$$$ 到 $$$j$$$ 的最短路径中的边数。另外,让我们表示 $$$k$$$ - 顶点 $$$x$$$ 的子树 - 顶点集 $$$y$$$ ,以满足接下来的两个条件:

- $$$x$$$ 是 $$$y$$$ 的祖先(每个顶点都是其自身的祖先);
- $$$d(x, y) \le k$$$。

Vasya 需要您处理 $$$m$$$ 查询。第 $$$i$$$ 查询是三重 $$$v_i$$$、$$$d_i$$$ 和 $$$x_i$$$。对于每个查询,Vasya 将值 $$$x_i$$$ 添加到 $$$d_i$$$ 子树 $$$v_i$$$ 中的每个顶点。

向 Vasya 报告所有值,在处理所有查询后写入树的顶点。

输入

第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) — 顶点 $$$x$$$ 和 $$$y$$$ 之间的边。保证给定的图是一棵树。

下一行包含单个整数 $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — 查询数。

接下来的 $$$m$$$ 行包含三个整数 $$$v_i$$$, $$$d_i$$$, $$$x_i$$$ ($$$1 \le v_i \le n$$$, $$$0 \le d_i \le 10^9$$$, $$$1 \le x_i \le 10^9$$$) — 的描述第 $$$i$$$ 个查询。

输出

打印 $$$n$$$ 整数。第 $$$i$$$ 个整数是处理所有查询后写入第 $$$i$$$ 个顶点的值。

示例

输入 #1

5
1 2
1 3
2 4
2 5
3
1 1 1
2 0 10
4 10 100

输出 #1

1 11 1 100 0

输入 #2

5
2 3
2 1
5 4
3 4
5
2 0 4
3 10 1
1 2 3
2 3 10
1 1 7

输出 #2

10 24 14 11 11

注意

在第一个示例中,顶点的初始值为 $$$0, 0, 0, 0, 0$$$。第一个查询后的值将等于 $$$1, 1, 1, 0, 0$$$。第二次查询后值将等于 $$$1, 11, 1, 0, 0$$$。第三次查询后值将等于 $$$1, 11, 1, 100, 0$$$。