题目描述

某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的 一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个 节点，编号分别为1、2、3、.... n。为了实时记录道路情况，需要在某些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能被监控到。

为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下， 部署监控设备的费用要尽可能少。

给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少?

例如: n=8,表示有8个节点(即道路交叉点或端点)，1到8号节点部署监控设备的费用分别为33、12、 30、22、 18、 10、31、28。道路分布图如下:

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

输入格式

第一行输入一个整数n $(2 ≤ n ≤ 10^4)$，表示城市中节点(即道路交叉点或端点)的数量

第二行输入n个整数(1 < 整数 ≤ 10^5) ，分别表示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