P9111 [福建省队集训2019] 最大权独立集问题

E.Space 喜欢出最大权独立集问题。 接下来，他还想出 $n$ 道最大权独立集问题。 E.Space 有 $n$ 个 AI，编号为 $1\sim n$。 开始第 $i$ 个 AI 里面存有一道 E.Space 事先出好的一道难度为 $d_i$ 的最大权独立集问题。 有些 AI 之间可以互相通信，对于所有的 $2 \le i \le n$，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。此外，其他对 AI 不可以互相通信。 E.Space 每次可以选择一个存有一道最大权独立集问题的 AI，把存在里面的题出出来，然后清除存在这个 AI 里的题。 在 E.Space 出题之后清除题目之前，AI 会把这道题发给能和它通信的所有 AI。 如果一个收到这道题的 AI 中已经存有一道最大权独立集问题，那么这个 AI 会把这个收到的题和原本存有的题结合起来，变成一道新的最大权独立集问题存起来。形式化地，如果这个 AI 原来存了一道难度为 $x$ 的最大权独立集问题，接着收到了一道难度为 $y$ 的最大权独立集问题，那么结合之后是一道难度为 $x+y$ 的最大权独立集问题。 如果一个收到题的 AI 中未存有题，那么这个 AI 会销毁收到的这个信息。 由于出题人的丧病心理，E.Space 想要出出来的 $n$ 道最大权独立集问题的难度之和尽量大。 他想叫你帮他解决这个问题，还说如果你成功在这场训练中解决了这个问题，那么在出那 $n$ 道最大权独立集问题的时候，他会在训练结束前 10 分钟切换至你的账号然后提交一份标程代码。

无

无

### 【样例解释 1】 一种最优的出题方案如下： 1. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $10$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,13,5$ ($*$ 表示该 AI 中没有最大权独立集问题，下同)。 2. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $13$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,*,18$。 3. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $11$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,18$。 4. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $18$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。 所以 $4$ 道题的难度之和为 $10+13+11+18=52$。 ### 【样例解释 2】 一种最优的出题方案如下： 1. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,3,*,5$。 2. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,8,*,*$。 3. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $8$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $9,*,*,*$。 4. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $9$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。 所以 $4$ 道题的难度之和为 $5+5+8+9=27$。 ### 【数据范围】 保证 $\left|d_i\right| \le 10^9$，$1 \le c_i \lt i$，$1\le n \le 400$。 **本题采用捆绑测试。** 对于编号为奇数的子任务，保证 $d_i \ge 0$。 子任务 $1,2$（$11 \times 2 = 22$ 分）： $n \le 9$。 子任务 $3,4$（$10 \times 2 = 20$ 分）： $n \le 19$。 子任务 $5,6$（$7 \times 2 = 14$ 分）： $n \le 50$，$c_i = i-1$。 子任务 $7,8$（$10 \times 2 = 20$ 分）： $c_i=i-1$。 子任务 $9,10$（$5 \times 2 = 10$ 分）： $n \le 50$。 子任务 $11,12$（$7 \times 2 = 14$ 分）： 无特殊限制。 ### 后记 听说 E.Space 的最大权独立集问题的难度是取了对数的？ 听说 E.Space 要把这 $n$ 道题结合成一道题出出来？ 听说 E.Space 不会把这些题出在训练里面？