← 返回题目列表

AtCoder · dwacon2018_prelims_d

D. 节省磁盘空间

中文机器翻译题面 查看原题

配点 : 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