小 A 和小 B 正在玩游戏。
他们面前有一个有根树森林，每个点 $u$ 有正整数点权 $A_u$。
小 A 和小 B 轮流操作，小 A 先手。当前操作的玩家需要选择恰好一个树根删除，获得它的点权，它的子树成为新的有根树，它的儿子成为新的树根。
所有点都删除后游戏结束，玩家的得分是由他删除的点权和。
两个玩家的目标都是最大化自己的得分，他们都采用最优策略。求最终小 A 的得分。
给定的初始局面包含恰好一棵 $n$ 个点的树，点编号从 $1$ 至 $n$，点 $1$ 为根。
输入格式
第一行一个正整数 $n$，表示点数。
第二行 $n$ 个正整数 $A_1,A_2,\dots,A_n$，表示每个点的点权。
接下来 $n-1$ 行给出了初始局面，每行两个正整数 $u,v$ 表示树中有一条连接 $u,v$ 的边。保证给定的是一棵树。
输出格式
输出一行一个整数，表示最终小 A 的得分。
样例一
input
5
1 5 3 2 4
1 2
1 3
2 4
2 5output
7样例二
见下发文件。
数据范围与约定
对于所有数据，$1\leq A_i\leq 10^9$。
| 子任务编号 | $n \le $ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $20$ | 无 | $20$ |
| $2$ | $1\,000$ | $20$ | |
| $3$ | $2 \times 10^5$ | A | $20$ |
| $4$ | B | $20$ | |
| $5$ | 无 | $20$ |
- 特殊性质 A：设 $p_i$ 为 $i$ 的父亲，那么对于所有 $2\leq i\leq n$ 有 $A_i\leq A_{p_i}$。
- 特殊性质 B：所有 $A_i$ 在 $[1,10^9]$ 的整数内等概率随机。