题目描述

一个大学里有 $n$ 个学生，他们回来参加聚会，不过它们之间的关系可能不好，如果关系直接不好就只能来一个，如果关系间接不好，两个都可以来，每个学生都有一个快乐指数，参加聚会就会加上快乐指数，求快乐指数最大是多少。

输入格式

一个数 $n$ 表示有多少个学生。 一行 $n$ 个整数，表示每个学生的快乐指数。 后面 $n-1$ 行，每行两个数 $u,v$ 表示 $u$ 和 $v$ 直接关系不好。

输出格式

一行 $1$ 个数，表示最大的快乐指数。

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

5

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^4$。