← 返回题目列表

AtCoder · abc222_f

I. 昂贵的费用

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

分数: 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