题目描述

小z探险家在一棵有 N 个节点的树上探险，每个节点可能藏有宝藏或陷阱。树的节点编号为 1 到 N，根节点为 1。树上的每个节点有以下属性：

宝藏节点（正整数）：节点上有价值为 v 的宝藏，收集后可获得该价值（每个宝藏只能收集一次）

陷阱节点（负整数）：进入节点会触发陷阱，扣除 | v | 的价值（陷阱只会触发一次，因为小z会毁掉陷阱）

普通节点（0）：无特殊效果

小z探险家从根节点出发，每次可以选择前往当前节点的任意一个子节点（但是选择了之后就不能选择其他子节点，回来必须原路返回，但是没有关系，他有天眼，能看到每个节点是哪个的情况），最终取得结点上的宝藏之后，原路返回到1出来。请计算小z探险家能获得的最大价值总和，如果所有可能路径的价值总和都为负数，输出 0（表示放弃探险）。

输入描述

1、输入树的节点数量 N，然后输入每个节点的价值（第 i 个数字对应节点 i 的价值）

2、接下来输入 N-1 条边，描述树的结构（保证输入是合法树）

3、输出最大价值总和（若为负则输出 0）

输入样例

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

输出样例

9

数据范围与提示

$1≤N≤1000$ 节点价值 v 的范围：$-100≤v≤100$ 树的深度不超过 1000（避免递归栈溢出问题，提示:用迭代 DFS）