题目背景

城市里的道路构成一棵无向树，每个路口安装监控都有对应的成本，每条道路两端至少有一处安装监控才能实现全覆盖，求最低总花费。

题目描述

给定有 $n$ 个路口的无根树，每个路口安装监控需要花费 $w_i$。 若在某个路口安装监控，所有与该路口直接相连的道路都会被覆盖。 规定每条道路至少有一端路口安装监控，请求出满足全覆盖要求的最小总花费。

输入描述

第一行一个整数 $n$，代表路口总数量。 第二行包含 $n$ 个整数，第 $i$ 个数字代表第 $i$ 号路口安装监控的花费 $w_i$。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示路口 $u$ 和 $v$ 之间连通一条道路。 路口编号范围：$1 \le u,v \le n$。

输出描述

输出单独一行一个整数，代表全覆盖所有道路需要的最小总花费。

输入样例1

4
5 1 3 4
1 2
2 3
2 4

输出样例1

1

样例解释：仅在2号路口安装监控，花费1，所有道路全部覆盖。

输入样例2

5
10 2 1 5 7
1 2
1 3
3 4
3 5

输出样例2

3

样例解释：选择2号、3号路口安装监控，总花费 $2+1=3$，为最优方案。

数据范围

$2 \le n \le 1500$ $1 \le w_i \le 1000$ 输入保证为合法树，不存在自环、重复道路。

。