【题目背景】

“清明时节雨纷纷，路上行人欲断魂。”

2075 年的清明没有春雨。在漫天飞雪的笼罩下，穿行在冰原间的，只有载着人类微薄希望的雪地车。

遥遥 4.22 光年的征途，对于地球这孤独的旅人而言，恐怕也是无比寂寞的吧。

【题目描述】

距离苏拉威西只有一百公里了，车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕，那是控制行星发动机的关键程序：春节十二响。他需要将其部署到电力 控制系统的一个芯片中。

“春节十二响”由 n 个子程序构成，第 i 个子程序所需的内存空间是 Mi。这 n 个子程序之间的调用关系构成了一棵以第 1 个子程序为根的树，其中第 i 个子程序在调 用树上的父亲是第 fi 个子程序。

由于内存紧张，电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 S 1, S 2, . . . , S k，并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系，则他们可以被分配到同一个段中，反之则不能。换言之，当且仅当a 和 b 在调用树上不. 是. 祖. 先.-后. 代. 关. 系. ，a 和 b 可以被分配到同一个段中一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值，所有段大小的和不能超过系统的内存大小。

现在艾莉芬想要知道，电力控制芯片至少要有多少内存，才能保证春节十二响的正确运行。即：最少需要多大的内存，才能通过先将. 内. 存. 分. 成. 若. 干. 个. 段. ，再把. 每. 个. 子. 程. 序.分. 配. 到. 一. 个. 段. 中. ，使得每. 个. 段. 中. 分. 配. 的. 所. 有. 子. 程. 序. 之. 间. 不. 存. 在. 祖. 先. -后. 代. 关. 系. 。

【输入格式】

从文件 spring.in 中读入数据。

第一行包含一个正整数 n 表示子程序的个数，其中 n ≤ 2 × 10^5。

第二行有 n 个用空格隔开的正整数 M1, M2, . . . , Mn，Mi 表示第 i 个子程序所需的内存空间。

第三行有 n − 1 个用空格隔开的正整数 f2, f3, . . . , fn，满足 fi < i，表示第 i 个子程序在调用树上的父亲是第 fi 个子程序。

【输出格式】

输出到文件 spring.out 中。仅一个整数，表示最小的内存需求。

【样例 1 输入】

5
10 20 20 30 30
1 1 2 2

【样例 1 输出】

60

【样例 1 解释】

在最优方案中，内存被划分为大小为 10，20，30 的三个段，其中第 1 个子程序被分配在第 1 个段中，第 2、3 个子程序被分配在第 2 个段中，第 4、5 个子程序被分配 在第 3 个段中。可以证明，不存在更优的方案。

【样例 2】

见选手目录下的 spring/spring2.in 与spring/spring2.ans。

【样例 3】

见选手目录下的 spring/spring3.in 与 spring/spring3.ans。

【子任务】

注意：在第 10、11、12 号测试点中，1 号子程序不. 一. 定. 是链的一个端点。

其中 M 是所有子内存需求的最大值，即 max{Mi}。 对于全部数据，1 ≤ n ≤ 2 × 10^5，1 ≤ M ≤ 10^9。

【提示】

艾莉芬经过仔. 细. 阅. 读. 题. 面、. 认. 真. 分. 析. 数. 据. 范. 围. 后，开始编写程序求解这个问题。

$ login Elephant

password: ********

艾莉芬，高级程序员。豫阳市第三工程组提醒您：

做题千万条，读题第一条；

编程不规范，爆零两行泪。

$ cd spring

$ ac spring

Spring Accepted. Score: 100/100.