题目描述

Bajtocia 正在准备把第一枚火箭发射到太空。Bajtazar 是太空计划的工作人员之一，负责安排宇航员登上火箭的过程。火箭内部由 $n$ 个舱室组成，舱室之间通过双向走廊连接，使得任意两个舱室之间恰好存在一条路径（如果途中不走回头路）。穿过每一条走廊需要 1 秒 bajtocki。舱室编号为 $1$ 到 $n$。火箭入口通向编号为 $1$ 的舱室。

将有 $n$ 名宇航员登上火箭，他们也编号为 $1$ 到 $n$。对每个 $1 \le i \le n$，编号为 $i$ 的宇航员将居住在编号为 $i$ 的舱室中。宇航员以 1 秒 bajtocki 的时间间隔依次进入火箭，并沿最短路径走到自己的舱室。编号为 $i$ 的宇航员到达自己的舱室后开始整理行李，这一过程恰好需要 $a_i$ 秒 bajtocki。

登船顺序必须满足：任何人都不需要经过一个已经有其住户在里面的舱室（无论该住户是否已经整理完行李）。

Bajtazar 的任务是规划登船流程，使其尽可能快，也就是说，使从第一名宇航员进入火箭到所有宇航员都整理完行李的时刻之间的时间尽可能短。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 500\ 000$），表示宇航员人数与舱室数量。第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）。$a_i$ 表示编号为 $i$ 的宇航员整理行李所需的时间。接下来 $n-1$ 行描述火箭内舱室的连接结构。每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$），表示编号为 $a$ 和 $b$ 的舱室之间有一条直接走廊相连。

输出格式

输出所有宇航员进入火箭并在舱室中安置完毕所需的最短时间。

样例数据

对于输入数据：

5
2 3 5 2 1
2 1
3 2
2 4
1 5

正确输出为：

7