题目描述

$N$ 个人的上下级关系构成一棵树。第 $1$ 个人为总监，第 $i$（$i\ge 2$）个人的直接上级为 $s_i$。

现在要给员工分配奖金。每个人的奖金可以是正整数，或者 $0$（没有奖金）。如果第 $i$ 个人获得了至少 $c_i$ 的奖金，下一年他的积极性会提高 $p_i$，否则积极性不会提高。

并非所有人都必须获得奖金，但是每个获得奖金的人的直接上级必须获得至少 $1$ 的奖金。

在发出的奖金总额不超过 $K$ 的前提下，求出积极性提高的总和最大值。

输入格式

$N$ $K$
$s_2$ $s_3$ $\ldots$ $s_N$
$p_1$ $p_2$ $\ldots$ $p_N$
$c_1$ $c_2$ $\ldots$ $c_N$

输出格式

一行一个非负整数，表示答案。

2 100
1
10 10
101 100

0

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

6

4 9
1 2 2
3 4 4 2
2 5 5 4

7

提示

样例解释

样例 $2$ 解释：

一个合法的奖金分配方案：员工依次获得的奖金为 $1,1,0,2,3$。

分配方案 $1,1,1,2,3$ 不合法，因为奖金超支了。

分配方案 $0,1,1,2,3$ 同样不合法，因为第 $2$ 个人获得了奖金，但其直接上级未获得。

数据范围

• $2\le N\le 5\, 000$；
• $1\le K\le 5\, 000$；
• $1\le p_i\le 10^5$；
• $1\le c_i\le 5\, 000$；
• $1\le s_i\lt i$；
• 输入的所有值均为整数。

子任务

子任务 $0$ 为样例。

其中，「$-$」表示「不保证」。

• 特殊性质 $\text{A}$：$c_i=1$，且 $j$ 是 $i$ 的上级 $\implies$ $p_j\ge p_i$。
• 特殊性质 $\text{B}$：$\forall 2\le i\le N$，$s_i=i-1$。

2025-06-03: 增加了一组 hack 数据