AT_abc222_f [ABC222F] Expensive Expense

题目描述

AtCoder 王国由 $N$ 个城市和 $N-1$ 条道路组成。
城市编号为城市 $1$、城市 $2$、$\dots$、城市 $N$。道路同样编号为道路 $1$、道路 $2$、$\dots$、道路 $N-1$。道路 $i$ 双向连接城市 $A_i$ 和 $B_i$，通过时需要支付 $C_i$ 的通行费。对于任意不同的城市对 $(i, j)$，都可以通过道路从城市 $i$ 到达城市 $j$。

现在，给定一个序列 $D = (D_1, D_2, \dots, D_N)$，其中 $D_i$ 表示在城市 $i$ 观光时需要的费用。此时，从城市 $i$ 到城市 $j$ 的旅行费用 $E_{i,j}$ 定义为：从城市 $i$ 出发，不重复经过同一条道路，前往城市 $j$ 时所需通行费之和，加上 $D_j$。

• 更严格地说，设 $i-j$ 之间的最短路径为 $i = p_0, p_1, \dots, p_{k-1}, p_k = j$，连接城市 $p_l$ 和 $p_{l+1}$ 的道路通行费为 $c_l$，则 $E_{i,j} = D_j + \displaystyle\sum_{l=0}^{k-1} c_l$。

请对于每个 $i$，求出以城市 $i$ 为起点前往其他城市时可能的最大旅行费用。

• 更严格地说，对于每个 $i$，求 $\max_{1 \leq j \leq N,\, j \neq i} E_{i,j}$。

输入格式

输入按以下格式从标准输入给出。

$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$ 行输出 $\max_{1 \leq j \leq N,\, j \neq i} E_{i,j}$。

输入输出样例 #1

输入 #1

3
1 2 2
2 3 3
1 2 3

输出 #1

8
6
6

输入输出样例 #2

输入 #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

输入 #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

说明/提示

限制条件

• $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)$
• 对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，都可以通过若干道路从城市 $i$ 到城市 $j$。
• 所有输入均为整数。

样例解释 1

对于所有城市的有序对 $(i, j)$，计算 $E_{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$

由 ChatGPT 4.1 翻译