AT_cf17_final_j.Tree MST

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

りんごさん有一棵包含 $N$ 个顶点的树。这棵树的 $N-1$ 条边中，第 $i$ 条边连接顶点 $A_i$ 与顶点 $B_i$ ，边权为 $C_i$ 。另外，顶点 $i$ 有一个权值 $X_i$ 。

我们定义 $f(u,v)$ 为“从顶点 $u$ 到顶点 $v$ 的距离”与“ $X_u + X_v$ ”的和。

请考虑一个包含 $N$ 个顶点的完全图 $G$ 。在 $G$ 中，顶点 $u$ 与顶点 $v$ 之间的边的代价为 $f(u,v)$ 。请你求出图 $G$ 的最小生成树的总代价。

输入从标准输入读入，格式如下：

$N\\$
$X_1$ $X_2$ $\cdots$ $X_N\\$
$A_1$ $B_1$ $C_1\\$
$A_2$ $B_2$ $C_2\\$
$\vdots\\$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出图 $G$ 的最小生成树的总代价。

输入#2

6
44 23 31 29 32 15
1 2 10
1 3 12
1 4 16
4 5 8
4 6 15

输出#2

输入#3

2
1000000000 1000000000
2 1 1000000000

输出#3

3000000000

限制条件

连接顶点 $1$ 和 $2$ 、顶点 $1$ 和 $4$ 、顶点 $3$ 和 $4$ ，分别的代价为 $5,8,9$ ，合计为 $22$ 。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?