题目背景

核桃村新通了一批高配置电脑，村长阿栓自告奋勇，开上小货车给每家每户送货上门。村民们一拿到电脑，就迫不及待地开始安装最近火爆的游戏「菜园物语」。

题目描述

核桃村有 $n$ 户人家，编号为 $1$ 至 $n$，村中有 $n-1$ 条路把所有房子连在一起，任意两户人家之间都只有唯一一条通路。阿栓住在 $1$ 号房子。

$n$ 台电脑被快递到了阿栓家，每户人家都应分到一台，送货的任务自然落到了阿栓肩上。他把所有电脑装上小货车出发了。车上的油恰好够他把每条路走两遍。每到一户人家，阿栓把电脑交给主人便立刻赶往下一户，交接不花时间；村民一拿到电脑就马上开始安装「菜园物语」，第 $i$ 户人家安装所需的时间为 $c_i$。送完所有电脑后，阿栓回到自己家装自己的「菜园物语」。

货车开过每条路恰好需要 $1$ 分钟。请你帮阿栓算算，从出发到所有村民（包括他自己）都装好游戏，最少需要多少分钟。

输入格式

第一行包含一个整数 $n(2 \leq n \leq 5\times 10^5)$，代表核桃村有多少户人家。

第二行包含 $n$ 个整数 $c_1, c_2, \cdots, c_n(1 \leq c_i \leq 10^9)$，每个数之间用单个空格隔开。$c_i$ 表示第 $i$ 户人家安装游戏所用的时间。

接下来的 $n-1$ 行每行代表一条路，包含两个整数 $a$ 和 $b$（$1 \leq a \lt b \leq n$），用一个空格隔开。

输出格式

输出一行一个整数，代表从出发到所有人都装好游戏的最少分钟数。

样例

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

11