题目描述

$Flysky$最近沉迷三角洲行动，在新的地图巴别塔中，有一些物资点相连，物资点上可能有一些物品，也可能有敌人。他给地图上的每个物资点都标注了收益$a_i$, 这些物资点由$n - 1$条路径相连。

现在$Flysky$位于物资点 $1$， 他可以在相连的两个物资点上任意移动，物资点可以重复到达。当他到达一个物资点时，他一定会获取上面的收益，同时这个点上面的收益会归零。由于$Flysky$很贪心，他想获得最大的收益，他现在需要你的帮助。

注: 数据保证物资点之间能相互到达。

输入格式

第一行给出一个数 $n$ $(2 ≤ n ≤ 2000)$

第二行给出 $n$ 个数 $a_i$, 代表第$i$个物资点的收益 $(-10^9 ≤ a_i ≤ 10^9)$

接下来的 $n - 1$行， 每行给出两个数 $u$，$v$ ， 代表物资点$u$和物资点$v$有一条路径相连

输出格式

输出一个数, 表示 $Flysky$ 的最大收益

样例

5
3 8 -6 7 3
1 2
1 3
3 4
3 5

15