4520 - 第十一课:间隔选点-树上版本

给定一颗n个节点的树,每个顶点有权值。

现在要求选出若干点,这些点不能有边直接相连,使得权值之和最大。
 

输入

第一行输入一个整数$ n(2 \le n \le 6*10^3) $。

第二行给出n个整数$ a_1, a_2, a_3, ..., a_n(-128 \le a_i \le 127) $,表示每个顶点的权值。

接下来n-1行,每行两个整数$ x_i, y_i (1 \le x_i, y_i \le n, x_i \ne y_i)$, 表示$ x_i, y_i $之间有一边条 $。

输入保证是一棵树。

输出

输出最大权值之和。

样例

输入

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

输出

5
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题