E-Tk的染色树_牛客周赛 Round 90

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一棵由 $n$ 个节点构成的树（节点编号为 $1 \sim n$ ）。
$\hspace{15pt}$ 每个节点有一个权值 $a_i$ 。初始时所有节点均为白色。
$\hspace{23pt}\bullet\,$ 你可以选择一个节点 $i$ ，花费 $2 \times a_i$ 的代价将其染成黑色。
$\hspace{23pt}\bullet\,$ 你可以选择任意两个不同节点 $i$ 和 $j$ ，花费 $a_i + a_j$ 的代价将它们之间的简单路径上的所有节点染成黑色（包括路径端点）。
$\hspace{15pt}$ 请你求出将整棵树染成黑色的最小总代价。

$\hspace{15pt}$ 树是指由 $n$ 个节点和 $n-1$ 条边构成的连通无环图。

$\hspace{15pt}$ 简单路径定义为在树上从节点 $u$ 到节点 $v$ 的路径，该路径不经过重复的节点或边。可以证明，在树上任意两个节点之间存在且仅存在一条简单路径。

输入描述:

第一行输入一个整数 ，表示树的节点个数。
第二行输入个整数 ，表示每个节点的权值。
接下来行，每行输入两个整数和，表示节点和节点之间有一条边。
保证输入的个节点构成一棵树。

输出描述:

输出一个整数，表示将整棵树染成黑色的最小代价。

示例1

输入

复制

输出

复制

说明

选择节点和，它们之间的简单路径包含了所有节点，并且是所有染色方案中代价最小的。
总代价为。