游戏内测

【题目描述】

某个土豪游戏招聘了N位游戏高手参与最新款游戏的内测。这N位游戏高手被安排进了N栋豪华别墅，这N栋别墅由N-1条道路连接成了一个联通图，显然，这片别墅区的连接方式应该是一棵树。

小x作为内测组组长，在1号别墅，现在他拿到了最新版的游戏，且要给其他N-1分发最新版的游戏，为了保密，游戏公司禁止通过网络传输游戏安装包，小x必须要骑单车给其他人送安装光盘。    

小x从一个别墅走到另一个别墅花费的时间为1分钟。一旦小x到了第i个别墅，他会立即把游戏光盘交给第i个人，第i个人会以迅雷不及掩耳之势开始安装，这两步因为很迅速，时间可以忽略，但是因为游戏内测要有普遍性，这N位游戏高手使用的电脑配置并不相同，第i台电脑安装游戏需要花费的时间为Ci。还是避免泄密，游戏公司要求每条道路小x最多只能经过两次。

小x必须给其他人送完游戏光盘后，回到自己的别墅才能开始安装自己那份游戏。

现在问，小x如何合理安排送光盘的顺序，使得N个人安装完游戏花费的时间最短，并计算这个时间。

【输入格式】

第一行一个整数N

第二行，N个用空格分开的整数，Ci表示第i个别墅安装游戏更新需要的时间。

接下来N-1行，每行两个整数Xi和Yi，表示别墅Xi和别墅Yi之间有一条道路相连。

保证Xi和Yi在[1..N]之间

【输出格式】

一行 一个整数

【样例输入】

6

1 8 9 6 3 2

1 3

2 3

3 4

4 5

4 6

【样例输出】

11

【提示】

小x送游戏的顺序应该是3,2,4,5,6.每个房间安装好游戏的时间为11，10,10,10,8,9。

【数据范围】

  40%  N<=7000

  100%  2<=N<=500000  Ci在[1..10^9]之间

【来源】

在此键入。