#PQJ963x4406. QOJ 963_4406

    ID: 3077 传统题 500ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2022树形DP深搜

QOJ 963_4406

标题: 独立集问题 - Problem - QOJ.ac

#4406. 独立集问题

Statistics

The problem was used in the following contests:

小 E 喜欢出最大权独立集问题。

接下来,他还想了 n 道最大权独立集问题。

但是和之前不一样,这回他想把 n 道题整合成一道题出出来。

小 E 有 n 个 AI,编号为 1∼n 。

开始第 i 个 AI 里面存有一道小 E 事先出好的一道难度为 di 的最大权独立集问题。

有些 AI 之间可以互相通信,对于所有的 2≤i≤n ,第 i 个 AI 可以和第 ci 个 AI 互相通信。其中 ci<i。所以,这些 AI 连成了一个树的形状。此外,其他对 AI 不可以互相通信。

小 E 每次可以选择一个存有一道最大权独立集问题的 AI,结合它能够直接互相通信的所有 AI 中的问题,变成一道新的最大权独立集问题。整合问题时总有难度损失,不可能是把所有问题的难度直接相加。这道新的最大权独立集问题的难度是那些能够直接互相通信的 AI 中的题目难度和减去原本存在该 AI 上的问题的难度。然后那些能够直接互相通信的 AI 中的问题难度会变成 0。

小 E 希望通过若干次操作,把 n−1 个 AI 中的题目难度都变成 0,然后把最后一个 AI 中的题目出出来。

由于出题人的丧病心理,小 E 想要出出来的最大权独立集问题的难度尽量大。

他想叫你帮他解决这个问题,还说如果你成功解决了这个问题,那么在出那道最大权独立集问题的时候,他会帮你提交一份标程代码。

输入格式

第一行一个正整数 n。

第二行 n 个整数,第 i 个表示 di。

第三行 n−1 个正整数,第 i 个表示 ci+1。

输出格式

一行一个整数表示答案。

样例数据

样例输入

4
-1 2 3 4
1 1 1

样例输出

10

子任务

保证 1≤n≤351493。

保证 1≤ci<i。

保证 |di|≤109。

子任务 1(13分):ci=i−1

子任务 2(6分):di>0

子任务 3(11分):n≤7

子任务 4(13分):n≤16

子任务 5(22分):n≤100

子任务 6(35分):无特殊性质