P12444 [COTS 2025] 发好奖 / Hijerarhija

$N$ 个人的上下级关系构成一棵树。第 $1$ 个人为总监，第 $i$（$i\ge 2$）个人的直接上级为 $s_i$。 现在要给员工分配奖金。每个人的奖金可以是正整数，或者 $0$（没有奖金）。如果第 $i$ 个人获得了至少 $c_i$ 的奖金，下一年他的**积极性**会提高 $p_i$，否则积极性不会提高。 并非所有人都必须获得奖金，但是每个获得奖金的人的直接上级必须获得至少 $1$ 的奖金。 在发出的奖金总额不超过 $K$ 的前提下，求出积极性提高的总和最大值。

无

无

### 样例解释 样例 $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$ 为样例。 其中，「$-$」表示「不保证」。 | 子任务编号 | $N\le$ | $K\le$ | 特殊性质 | 得分 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $20$ | $-$ | $-$ | $7$ | | $2$ | $-$ | $-$ | $\text{A}$ | $9$ | | $3$ | $-$ | $-$ | $\text{B}$ | $14$ | | $4$ | $500$ | $500$ | $-$ | $19$ | | $5$ | $100$ | $-$ | $-$ | $21$ | | $6$ | $-$ | $-$ | $-$ | $30$ | - 特殊性质 $\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 数据