QOJ.ac

QOJ

Time Limit: 0.2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 4406. 独立集问题

Statistics

小 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 想要出出来的最大权独立集问题的难度尽量大。

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

输入格式

第一行一个正整数 $n$。

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

第三行 $n-1$ 个正整数,第 $i$ 个表示 $c_{i+1}$。

输出格式

一行一个整数表示答案。

样例数据

样例输入

4
-1 2 3 4
1 1 1

样例输出

10

子任务

保证 $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分):无特殊性质