题目描述

在一棵树上有若干个节点，每个节点都有一个权值。现在需要从这些节点中选择一部分节点，使得任意两个选中的节点不相邻（即没有直接的边连接）。请计算选中节点的最大权值之和。

输入描述

第一行包含一个整数n，表示树的节点数量。 第二行包含n个整数，分别表示每个节点的权值，第i个整数表示节点i的权值（节点编号从1到n）。 接下来n-1行，每行包含两个整数u和v，表示节点u和节点v之间有一条边。

输出描述

输出一个整数，表示选中节点的最大权值之和。

输入样例

3
1 2 3
1 2
2 3

输出样例

4

数据范围

1 ≤ n ≤ 1000 每个节点的权值为非负整数，且不超过10000