六、某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的 一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个 节点，编号分别为1、2、3、.... n。为了实时记录道路情况，需要

六、某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的 一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个 节点，编号分别为1、2、3、.... n。为了实时记录道路情况，需要在某 些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能 被监控到。VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下， 部署监控设备的费用要尽可能少。VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到 的最少花费是多少?VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

例如: n=8,表示有8个节点(即道路交叉点或端点)，1到8号节 点部署监控设备的费用分别为33、12、 30、22、 18、 10、31、28。道 路分布图如下:VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

根据观察可得，在2号和3号节点处部署监控设备，可以使所有道路都 能被监控到，并且花费最少，最少花费为42。VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一行输入一个整数n (2≤n≤) ，表示城市中节点(即道路交 叉点或端点)的数量VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第二行输入n个整数(1<整数≤) ，分别表示1号到n号节 点部署监控设备的费用VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来n-1行，每行输入两个整数a, b,表示节点a和节点b 之间有一条道路VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出一个整数，表示要使所有道路均能被监控到的最少花费。VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入样例VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

8VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
33 12 30 22 18 10 31 28VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 2VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 3VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 4VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 5VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 6VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 7VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 8VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出样例VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

42VWD100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库