[问题描述]
众所周知，Alice 和 Bob 是一对宿敌，每次博弈游戏中 Alice 和 Bob 总绞尽
脑汁企图战胜对手，而且很不公平地，每次都是 Alice 先手。
然而他们都看上了大 M 种的一棵巧克力树，为了取得更多的巧克力，他们决
定联手合作。
大 M 的巧克力树由 n 个节点组成，每个节点 i 上都有 v[i]个巧克力，巧克
力树上有 n-1 条树枝连接这整棵树（保证任意两点间存在一条路径）。
Alice 和 Bob 一开始都可以选择一个出发起点并获得该节点上的所有巧克
力，当然，Alice 先选。接下来，Alice 和 Bob 会依次移动到自己节点相邻的节
点上，并获得该节点上的所有巧克力。但是，任意节点都只能被经过一次，若
Alice 走过某个节点 x，则 Bob 不能到达这个节点，当然 Alice 也不能走回 x。
请问他们总共最多能获得多少巧克力？
[输入格式]
第一行 1 个整数 n，表示节点个数；
第二行 n 个整数，表示 v[1..n]；
接下来 n-1 行，每行两个整数 x 和 y，表示节点 x 与节点 y 之间有一条树枝
相连。
[输出格式]
输出一行一个数，为总共能获得的最多的巧克力数。
[输入样例 1]
9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
[输出样例 1]
25
[输入样例 2]
2
10 20
1 2
[输出样例 2]
30
[数据规模]
对于 20%的数据，n<=50；
对于 50%的数据，n<=5000；
对于 100%的数据，n<=100000，1<=v[i]<=10^9。