配点 : 600 点
問題文
Niwango 是 dwango 员工,是一名参与应用程序开发的工程师。 Niwango-kun 每天都会构建、测试和部署开发的应用程序。为了简化工作,Niwango 决定编写一个程序来正确执行这些相关任务。
任务是 N 可用, 当您运行第 i 个任务时,结果为 x_i 写入磁盘的 MB 数据。然而,一个任务可能依赖于另一个任务,除非所有依赖任务的执行结果都写入磁盘,否则该任务无法执行。 具有依赖于 i 番目 (2 \leq i \leq N) 的任务的任务是 我们知道 a_i 。
N 任务的依赖关系形成一个连接的有向树。也就是说,对于任何给定的任务,只有一个任务将该任务作为依赖项。然而,第一个任务是一个例外,它不依赖于任何任务。第一个任务直接或间接依赖于所有其他任务。
Niwango-kun 的目的是执行第一个任务并将结果写入磁盘。二王后君也想尽可能地节省计算资源。二王后君执行任何任务后,立即 您可以选择并删除 0 或多个任务执行结果。我还想节省时间并降低复杂性,因此我不会多次运行同一任务。
Niwango需要多少磁盘才能获取第一个任务的执行结果?按照适当的顺序执行任务并删除执行结果,以尽量减少过程中最大的磁盘使用量(写入磁盘的执行结果总量)。请输出最小值(MB)。
制約
- 1 \leq N \leq 20
- 1 \leq x_i \leq 1,000,000 (1 \leq i \leq N)
- 1 \leq a_i \leq i - 1 (2 \leq i \leq N)
入力
输入是按以下格式从标准输入给出的。
N
x_{1} x_{2} x_{3} ... x_{N}
a_{2} a_{3} ... a_{N}
出力
打印答案。
入力例1
5 3 5 2 4 6 1 1 2 2
出力例1
15
| 行動 | 磁盘消耗 |
|---|---|
| 执行任务4 | 4 (= 4) |
| 执行任务5 | 10 (= 4 + 6) |
| 执行任务2 | 15 (= 4 + 6 + 5) |
| 删除任务 4 和 5 的结果 | 5 (= 5) |
| 执行任务3 | 7 (= 5 + 2) |
| 执行任务1 | 10 (= 5 + 2 + 3) |
这将导致在此过程中最大磁盘消耗为 15 MB。这是该输入的最佳选择。
入力例2
2 3 5 1
出力例2
8
入力例3
5 1 2 3 4 5 1 2 3 4
出力例3
9