题目背景

学校有 $n$ 个社团，编号 $1 \sim n$，社团之间形成了一个树形结构。 编号 $1$ 是总社团，其他社团有唯一的上级社团。

每学期学校会举办"社团展示日"。如果某个社团被选为参展社团， 那么它的上级社团和下级社团都不能参展（避免场地冲突）。

每个社团都有一个"活跃值"，学校想选出一组参展社团，使得活跃值总和尽可能大。

题目描述

给定一棵 $n$ 个节点的树，根节点为 $1$，每个节点有一个正整数权重 $a_i$。

选中一个节点后，它的父节点和子节点都不能被选中。

求能选中的节点权重之和的最大值。

输入格式

第一行一个正整数 $n$，表示社团个数。

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个社团的活跃值。

接下来 $n-1$ 行，每行两个整数 $u, v$，表示社团 $u$ 和 $v$ 有上下级关系。

输出格式

输出一个整数，表示最大活跃值总和。

样例输入

7
4 1 1 5 3 6 2
1 2
1 3
2 4
2 5
3 6
3 7

样例输出

20

样例解释

树的结构如下：

      1(4)
     / \
   2(1) 3(1)
   / \   / \
 4(5)5(3) 6(6)7(2)

最佳方案：选中节点 $1,4,5,6,7$，活跃值总和 $=4+5+3+6+2=20$。

检查限制：

• $1$ 被选 → 下级 $2,3$ 不能选 ✅
• $4,5$ 被选 → 上级 $2$ 已不能选 ✅
• $6,7$ 被选 → 上级 $3$ 已不能选 ✅

注意：选了根节点 $1$ 后，直系下级 $2,3$ 不能选，但孙子节点 $4,5,6,7$ 仍然可以选。

数据范围

$1 \le n \le 500$，$1 \le a_i \le 1000$