题目描述

译自 COCI 2020/2021 Contest #2 T4「Sjekira」

Mirko 厌倦了他在一家大型跨国软件公司担任 CEO 的生活。带着几百万美元的资产，他决定辞掉自己的工作，转而搬到一个叫做 Gorski Kotar 的小村庄去过一个清闲的生活。不幸的是，那里的冬天寒冷又漫长，生活并不容易。他的邻居都在二战以前出生的事实，注定了他只能自己去砍柴。

今天，Mirko 要开始砍第一棵树。在开始工作之前，他标记了这棵树各部分的硬度。

作为一名程序员，Mirko 很快注意到这棵树的各部分形成了一个树形结构。他还发现，砍断这棵树上某条边对他斧头的损害值，等于砍断这条边后形成的两个联通分量中，各联通分量中硬度最大值的和。

因为 Mirko 只有一把斧头，因此他希望砍掉这棵树对斧头的损害值最小。现在你需要帮他求出，将整棵树切割成单个部分对斧头造成的最小损害值。

输入格式

输入第一行一个整数 $n$，代表这棵树由 $n$ 部分组成。

第二行 $n$ 个整数，第 $i$ 个整数 $t_i$ 表示第 $i$ 部分的硬度。

接下来 $n-1$ 行，每行两个整数 $u,v$，代表 $u$ 和 $v$ 这两个部分间有一条边相连。

输出格式

输出一个整数，代表 Mirko 将整棵树切割成单个部分对斧头造成的最小损害值。

样例 1

• 输入： $3$ $1$ $2$ $3$ $1$ $2$ $2$ $3$
• 输出：$8$

一种方案是先砍掉 $(1,2)$ 边，花费为 $1+3=4$，再砍掉 $(2,3)$ 边，花费为 $2+3=5$，总花费为 $9$，但该方案不是最优方案。

最优方案是先砍掉 $(2,3)$ 边，花费为 $2+3=5$，再砍掉 $(1,2)$ 边，花费为 $1+2=3$，总花费为 $8$。

样例 2

• 输入： $4$ $2$ $2$ $3$ $2$ $1$ $3$ $3$ $2$ $4$ $3$
• 输出：$15$

样例 3

• 输入： $5$ $5$ $2$ $3$ $1$ $4$ $2$ $1$ $3$ $1$ $2$ $4$ $2$ $5$
• 输出：$26$

数据范围与提示

所有数据均满足：$1 \leq n \leq 10^5$，$1 \leq t_i \leq 10^9$。

各子任务的分值和约束条件如下：