g6-07528. 负权最大权独立集 未做

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点，结点 $i$ 有权值 $w_i$（可以为负）。

选择若干结点，要求任意一对父子不能同时被选，求所选结点权值和的最大值。允许一个都不选（权值和 $0$）。

第一行一个整数 $n$。

第二行 $n$ 个整数 $w_1,\dots ,w_n$。

第三行 $n-1$ 个整数 $f_2,\dots ,f_n$（$n=1$ 时该行为空）。

输入：

3
-5 10 -3
1 1

输出：

10

只选 $2$ 号（$10$），不选负权结点。

• 对于 $30\%$ 的测试点，$1\le n\le 20$；
• 对于 $60\%$ 的测试点，$1\le n\le 2000$；
• 对于全部测试点，$1\le n\le 10^5$，$-10^9\le w_i\le 10^9$。