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

Luogu

IDLGP9111

Time1500ms

Memory1024MB

DifficultyP6

2019福建O2优化背包 DP树形 DP

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 分钟切换至你的账号然后提交一份标程代码。 ## Input 第一行一个正整数 $n$。第二行 $n$ 个整数，第 $i$ 个表示 $d_i$。第三行 $n-1$ 个整数，第 $i$ 个表示 $c_{i+1}$。 ## Output 一行一个整数，表示最大的难度之和。 [samples] ## Note ### 【样例解释 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 不会把这些题出在训练里面？

Samples

Input #1

4
1 10 3 5
1 2 3

Output #1

Input #2

4
1 -2 5 5
1 2 2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[福建省队集训2019] 最大权独立集问题",
    "description": {
      "content": "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$ 个 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9111"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "E.Space 喜欢出最大权独立集问题。\n\n接下来，他还想出 $n$ 道最大权独立集问题。\n\nE.Space 有 $n$ 个 AI，编号为 $1\\sim n$。\n\n开始第 $i$ 个 AI 里面存有一道 E.Space 事先出好的一道难度为 $d_i$ 的最大权独立集问题。\n\n有些 AI 之间可以互相通信，对于所有的 $2 \\le i \\le n$，第 $i$ 个 AI 可以和第 $c_i$ 个 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments