07673. 树的最大独立集 未做

给定一棵有 $n$ 个结点的树，结点编号为 $1$ 到 $n$，其中第 $i$ 个结点有一个整数权值 $w_i$（可以为负数）。

请选出若干个结点组成集合 $S$，要求 $S$ 中任意两个结点都不相邻（即不存在一条边同时连接 $S$ 中的两个结点），使得 ${\sum }_{i\in S}{w}_i$ 最大。

允许一个结点都不选。此时 $S$ 为空集，规定其权值和为 $0$，并且空集本身也满足「任意两点不相邻」的要求。

第一行一个正整数 $n$。

第二行 $n$ 个整数 $w_1,w_2,\dots ,w_n$，相邻两个整数之间用一个空格隔开。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边。输入保证这些边构成一棵树。

输出一行一个整数，表示满足要求的点集中最大的权值和。

样例输入

5
-5 4 6 -2 3
1 2
1 3
3 4
3 5

样例输出

10

样例解释

这棵树以 $1$ 为根时：结点 $2$ 是 $1$ 的儿子，结点 $3$ 是 $1$ 的儿子，结点 $4,5$ 都是 $3$ 的儿子。

选取的集合 $S$	是否合法	权值和
$\varnothing$	合法	$0$
$\{3\}$	合法	$6$
$\{2,3\}$	合法（$2,3$ 不相邻）	$4+6=10$
$\{2,4,5\}$	合法	$4+(-2)+3=5$
$\{1,4\}$	合法	$(-5)+(-2)=-7$
$\{1,3\}$	不合法（$1,3$ 相邻）	—

所有合法集合中权值和最大的是 $S=\{2,3\}$，答案为 $10$。

对于全部测试数据：

• $1\le n\le 2000$；
• $-10^9\le w_i\le 10^9$；
• $1\le u,v\le n$，且输入的 $n-1$ 条边恰好构成一棵树。

注意：答案可能超过 $32$ 位整数的表示范围。