第3题：树上选点 (choose)

• 输入：choose.in
• 输出：choose.out
• 时间限制：2 s
• 内存限制：512 MB

题目描述

给定一棵大小为 $n$ 的有根树，树上结点编号从 $1$ 到 $n$。树根为结点 $1$，每个点都有一个点权，第 $i$ 个点的点权为 $V_i$。

你需要找出若干个点 $P_i$，使得：

1. 每两个点 $P_x, P_y$ 互不相邻；
2. 每两个点 $P_x, P_y$ 与树根的距离互不相同；
3. 找出的点的点权之和尽可能大。

请输出找到的这些点的点权和的最大值。

输入格式

输入的第一行包含一个整数 $n$。

第二行包含 $n - 1$ 个整数 $F_2, F_3, \ldots, F_n$，相邻整数之间使用一个空格分隔，分别表示第 $2$ 至 $n$ 个结点的父结点编号（其中 $F_i$ 表示结点 $i$ 的父结点编号）。

第三行包含 $n$ 个整数 $V_1, V_2, \ldots, V_n$，相邻整数之间使用一个空格分隔，分别表示每个结点的点权（其中 $V_i$ 表示结点 $i$ 的点权）。

输出格式

输出一行包含一个整数，表示答案。

输入输出样例 #1

输入 #1

5
1 2 3 2
2 1 9 3 5

输出 #1

11

输入输出样例 #2

输入 #2

10
1 1 1 2 2 3 3 4 5
8 7 6 9 5 4 3 2 3 2

输出 #2

15

说明/提示

【数据规模与约定】

对于 $40\%$ 的评测用例，$n \le 5000$

对于所有评测用例，$1 \le n \le 2 \times 10^5,\quad 1 \le F_i < i,\quad 1 \le V_i \le 10^4$