题目描述

公司里有 $n$ 个人，编号从 $1$ 到 $n$ ，他们中除了大boss以外，每个人都有一个直属领导。
现在需要邀请一些人来参加一个公司聚会，但是如果一个人的直属领导参加了聚会，那么他就不会参加聚会；同理，如果一个人的直属下属参加了聚会，那么他也不会参加聚会。
每个人都有一个欢乐值。现在请你安排参加聚会的人，使得在满足上述要求（即不存在参加聚会的两个人 $a$ 和 $b$ 且 $a$ 是 $b$ 的直属上司）的前提下这些人的欢乐值之和最大。

输入格式

输入的第一行包含一个整数 $n(1 \le n \le 6000)$，用于表示公司的人数。
接下来 $n$ 行，每行包含一个整数，第 $i$ 行的整数用于表示第 $i$ 个人的欢乐值。
接下来 $n−1$ 行，每行包含两个整数 $a$ 和 $b$ ，以一个空格分隔，用于表示 $a$ 的直属上司是 $b$。

输出格式

输出一个整数，用于表示参加聚会的人的最大欢乐值。

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

5