g7-07674. 没有上司的舞会 未做

某公司有 $n$ 名职员，编号为 $1\sim n$，其中 $1$ 号职员是公司的最高领导。除最高领导外，每名职员都有且仅有一位直接上司，上司关系构成一棵以 $1$ 号职员为根的树。

公司要举办一场舞会。每名职员 $i$ 有一个快乐指数 $a_i$。如果职员 $i$ 参加舞会，就会为舞会增加 $a_i$ 的快乐值。但为了让舞会气氛轻松，任意一名职员都不能与自己的直接上司同时参加舞会。

请你选择一组参加舞会的职员（可以一个人都不选），使得任意两名参加者都不是直接上下级关系，并最大化参加者的快乐指数之和。

第一行一个正整数 $n$，表示职员人数。

第二行 $n$ 个整数 $a_1,a_2,\dots ,a_n$，依次表示每名职员的快乐指数。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示职员 $u$ 与职员 $v$ 之间存在直接上下级关系。保证这些边构成一棵以 $1$ 号职员为根的树。

输出一行一个整数，表示参加舞会的职员的快乐指数之和的最大值。

输入：

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

输出：

5

样例说明：选择 $1,4,5,6,7$ 号职员参加舞会。其中 $1$ 与 $2,3$ 是直接上下级关系，$2$ 与 $4,5$ 是直接上下级关系，$3$ 与 $6,7$ 是直接上下级关系；所选职员中任意两人都不是直接上下级关系。快乐值之和为 $1+1+1+1+1=5$，可以证明不存在更大的方案。

• $1\le n\le 2000$；
• $-10^4\le a_i\le 10^4$；
• $1\le u,v\le n$，输入保证 $n-1$ 条边构成一棵以 $1$ 号职员为根的树；
• 允许一个人都不选，此时快乐值之和为 $0$。