← 返回题目列表

AtCoder · asaporo2_e

E. 黑猫部署

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

分数: 800 点

问题陈述

Snuke Festival 2017 将在树上举行 N 顶点编号 1,2, ...,N。 的 i第一条边连接顶点 a_i 和 b_i,并且有 喜悦 c_i.

工作人员是 Snuke 并且 N-1 黑猫。 Snuke 将在某个顶点设立总部,并从那里向对方部署一只猫 N-1 顶点。

对于每个顶点,计算 善良 当总部设立在该顶点时。 总部设立在 Vertex 的美好 i 计算如下:

  • 让 X=0.
  • 对于每个整数 j 之间 1 和 N (含)除外 i,执行以下操作:
    • 添加 c to X,其中 c 是从 Vertex 开始的路径上边的最小快乐度 i 到顶点 j.
  • 漂亮度是最终的值 X.

约束

  • 1 \leq N \leq 10^{5}
  • 1 \leq a_i,b_i \leq N
  • 1 \leq c_i \leq 10^{9}
  • 给定的图是一棵树。
  • 所有输入值均为整数。

部分分数

  • 在测试集中值得 200 点, N \leq 1000.
  • 在测试集中值得 200 点, c_i \leq 2.

输入

输入由标准输入按以下格式给出:

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}

输出

打印 N 行。的 i- 当总部设置在Vertex时,第行必须包含niceness i.


示例输入 1

3
1 2 10
2 3 20

示例输出 1

20
30
30
  • 下图为各顶点设立总部的情况 1, 2 和 3.
  • 边上方的数字表示该边的快乐度,顶点下方的数字表示从总部到该顶点的路径上边的最小快乐度。
1ee10aa2a1bf5e43e05161f37d88bdc1.png

示例输入 2

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2

示例输出 2

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20

示例输入 3

19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14

示例输出 3

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370