分数: 500 点
问题陈述
AtCoder 王国由 N 城镇和 N-1 道路。
城镇被标记为城镇 1, 镇 2, \dots, 镇 N。
同样,道路被标记为 Road 1, 路 2, \dots, 路 N-1。
道路 i 连接城镇 A_i 和 B_i 双向,您必须支付 C_i 去经历它。对于每对不同的城镇 (i, j), 可以从城镇前往 A_i 到镇 B_j 通过道路。
给你一个序列 D = (D_1, D_2, \dots, D_N),其中 D_i 是在城镇观光的费用 i。 让我们定义旅行成本 E_{i,j} 来自城镇 i 到镇 j 为从城镇出发时发生的总通行费 i 到镇 j,加上 D_{j}.
- 更正式地说, E_{i,j} 定义为 D_j + \displaystyle\sum_{l=0}^{k-1} c_l,其中之间的最短路径 i 和 j is i = p_0, p_1, \dots, p_{k-1}, p_k = j 以及连接城镇的道路通行费 p_{l} 和 p_{l+1} is c_l.
对于每个 i,找出从城镇出发时可能的最大旅行成本 i 到另一个城镇。
- 更正式地说,对于每个 i,查找 \max_{1 \leq j \leq N, j \neq i} E_{i,j}.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N-1)
- 1 \leq B_i \leq N (1 \leq i \leq N-1)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq N-1)
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 可以从城镇出发 i 到镇 j 通过一些道路,对于一对整数 (i,j) 这样 1 \leq i \lt j \leq N.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
D_1 D_2 \dots D_N
输出
打印 N 行。的 i- 第行应包含 \displaystyle \max_{1 \leq j \leq N, j \neq i} E_{i,j}.
示例输入 1
3 1 2 2 2 3 3 1 2 3
示例输出 1
8 6 6
的值 E_{i,j} 对于每个有序的城镇对 (i,j) 如下。
- E_{1,2} = 2 + 2 = 4
- E_{1,3} = 5 + 3 = 8
- E_{2,1} = 2 + 1 = 3
- E_{2,3} = 3 + 3 = 6
- E_{3,1} = 5 + 1 = 6
- E_{3,2} = 3 + 2 = 5
示例输入 2
6 1 2 3 1 3 1 1 4 4 1 5 1 1 6 5 9 2 6 5 3 100
示例输出 2
105 108 106 109 106 14
示例输入 3
6 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 1 2 3 4 5 6
示例输出 3
5000000006 4000000006 3000000006 3000000001 4000000001 5000000001