题目描述

这又是一个树论问题。给定一棵树，每个节点有一个罚值，每条边有一个权重。任意两个节点之间简单路径的代价定义为路径上所有边的权重之和，加上两个端点节点的罚值之积。注意，路径可以包含 $0$ 条边，此时路径的代价就是该节点罚值的平方。

对于每个节点，请计算从该节点出发的所有路径中的最小代价。最终答案等于所有这些最小代价的总和。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含一个整数 $n$（$1 \leq n \leq 200{,}000$），表示节点的数量。下一行包含 $n$ 个空格分隔的整数 $p$（$1 \leq p \leq 1{,}000{,}000$），按顺序表示每个节点的罚值。接下来的 $n-1$ 行，每行包含三个空格分隔的整数 $i$、$j$ 和 $w$（$1 \leq i \leq n$，$1 \leq j \leq n$，$i \neq j$，$1 \leq w \leq 1{,}000{,}000$），表示节点 $i$ 和节点 $j$ 之间有一条权重为 $w$ 的边。

输出格式

输出一个整数，表示每个节点的最低代价路径的代价之和。

5
9 7 1 1 9
3 2 8
5 2 10
4 3 10
2 1 2

63

提示

翻译由 DeepSeek V3.2 完成