[CTS2022] 独立集问题

Luogu

IDLGP8258

Time1000ms

Memory512MB

DifficultyP7

2022树形 DPCTSC/CTS

小 E 喜欢出最大权独立集问题。接下来，他还想了 $n$ 道最大权独立集问题。但是和之前不一样，这回他想把 $n$ 道题整合成一道题出出来。小 E 有 $n$ 个 AI，编号为 $1\sim n$ 。开始第 $i$ 个 AI 里面存有一道小 E 事先出好的一道难度为 $d_i$ 的最大权独立集问题。有些 AI 之间可以互相通信，对于所有的 $2 \le i \le n$ ，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。其中 $c_i<i$。所以，这些 AI 连成了一个树的形状。此外，其他对 AI 不可以互相通信。小 E 每次可以选择一个存有一道最大权独立集问题的 AI，结合它能够直接互相通信的所有 AI 中的问题，变成一道新的最大权独立集问题。整合问题时总有难度损失，不可能是把所有问题的难度直接相加。这道新的最大权独立集问题的难度是那些能够直接互相通信的 AI 中的题目难度和减去原本存在该 AI 上的问题的难度。然后那些能够直接互相通信的 AI 中的问题难度会变成 $0$。小 E 希望通过若干次操作，把 $n-1$ 个 AI 中的题目难度都变成 $0$，然后把最后一个 AI 中的题目出出来。由于出题人的丧病心理，小 E 想要出出来的最大权独立集问题的难度尽量大。他想叫你帮他解决这个问题，还说如果你成功解决了这个问题，那么在出那道最大权独立集问题的时候，他会帮你提交一份标程代码。 ## Input 第一行一个正整数 $n$。第二行 $n$ 个整数，第 $i$ 个表示 $d_i$。第三行 $n-1$ 个正整数，第 $i$ 个表示 $c_{i+1}$。 ## Output 一行一个整数表示答案。 [samples] ## Note 保证 $1\le n\le 351493$。保证 $1\le c_i <i$。保证 $|d_i|\le 10^9$。子任务 1（13 分）：$c_i=i-1$。子任务 2（6 分）：$d_i>0$。子任务 3（11 分）：$n\le 7$。子任务 4（13 分）：$n\le 16$。子任务 5（22 分）：$n\le 100$。子任务 6（35 分）：无特殊性质。

Samples

Input #1

4
-1 2 3 4
1 1 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[CTS2022] 独立集问题",
    "description": {
      "content": "小 E 喜欢出最大权独立集问题。 接下来，他还想了 $n$ 道最大权独立集问题。 但是和之前不一样，这回他想把 $n$ 道题整合成一道题出出来。 小 E 有 $n$ 个 AI，编号为 $1\\sim n$ 。 开始第 $i$ 个 AI 里面存有一道小 E 事先出好的一道难度为 $d_i$ 的最大权独立集问题。 有些 AI 之间可以互相通信，对于所有的 $2 \\le i \\le n$ ，第 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8258"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 E 喜欢出最大权独立集问题。\n\n接下来，他还想了 $n$ 道最大权独立集问题。\n\n但是和之前不一样，这回他想把 $n$ 道题整合成一道题出出来。\n\n小 E 有 $n$ 个 AI，编号为 $1\\sim n$ 。\n\n开始第 $i$ 个 AI 里面存有一道小 E 事先出好的一道难度为 $d_i$ 的最大权独立集问题。\n\n有些 AI 之间可以互相通信，对于所有的 $2 \\le i \\le n$ ，第 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments