题目背景

拿到卷轴后，其光芒指引王老师来到一棵巨大的神树前。只有激活神树，才能打开通往赛博王国的传送阵。

题目描述

神树可以看作一棵有 $N$ 个节点的无根树。每个节点 $i$ 上可以放置一颗魔力石，放置后会产生 $W_i$ 的魔力值。但神树的规则是：不能在两个相邻的节点上同时放置魔力石。请你帮王老师计算，最多能激活多少总魔力值？

输入格式

第一行一个整数 $N$，表示神树的节点数。 第二行 $N$ 个整数，第 $i$ 个数表示 $W_i$。 接下来 $N-1$ 行，每行两个整数 $u, v$，表示节点 $u$ 和 $v$ 之间有一条树枝相连。

输出格式

一个整数，表示能激活的最大总魔力值。

样例输入

5
1 2 3 4 5
1 2
1 3
2 4
2 5

样例输出

12

解释

选择节点 3, 4, 5，不含相邻节点，总魔力值为 3 + 4 + 5 = 12。

数据规模与约定

对于 100% 的数据，$1 \le N \le 10^5$，$1 \le W_i \le 10^4$。