题目描述：

某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有 n 个节点，编号分别为 1、2、3、...、n。
为了实时记录道路情况，需要在某些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少？
例如：n = 8，表示有 8 个节点（即道路交叉点或端点），1 到 8 号节点部署监控设备的费用分别为 33、12、30、22、18、10、31、28。道路分布图如下：

根据观察可得，在 2 号和 3 号节点处部署监控设备，可以使所有道路都能被监控到，并且花费最少，最少花费为 42。

输入描述：

第一行输入一个整数 n（2≤n≤104），表示城市中节点（即道路交叉点或端点）的数量
第二行输入 n 个整数（1≤整数≤105），分别表示 1 号到 n 号节点部署监控设备的费用
接下来 n - 1 行，每行输入两个整数 a，b，表示节点 a 和节点 b 之间有一条道路

输出描述：

输出一个整数，表示要使所有道路均能被监控到的最少花费

8
33 12 30 22 18 10 31 28
1 2
1 3
2 4
2 5
2 6
3 7
3 8

42

Limitation

1s, 1024KiB for each test case.