题目描述

某公司有 $n$ 个服务站点，这些站点之间由 $n-1$ 条道路连接，并且任意两个站点之间都能通过道路互相到达。也就是说，站点和道路构成一棵树。

第 $i$ 个站点的重要度为 $w_i$。公司要选择其中一个站点作为配送中心。若配送中心选在节点 $p$，则总运输代价定义为：

其中 $\mathrm{dis}(i,p)$ 表示节点 $i$ 到节点 $p$ 的边数距离。请你求出可以达到的最小总运输代价。

输入格式

第一行包含一个整数 $n$，表示树的节点数。 第二行包含 $n$ 个整数 $w_1,w_2,\dots,w_n$，其中 $w_i$ 表示节点 $i$ 的重要度。 接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示节点 $u$ 与节点 $v$ 之间有一条边。

输出格式

输出一个整数，表示最小总运输代价。

样例

输入数据1

4
1 2 3 4
1 2
2 3
3 4

输出数据1

8

输入数据2

4
3 2 1 4
1 2
2 3
3 4

输出数据2

12

提示

数据范围与提示

提示