A5834 · 「十二省联考 2019」春节十二响

题目描述

距离苏拉威西只有一百公里了，车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕，那是控制行星发动机的关键程序：春节十二响。他需要将其部署到电力控制系统的一个芯片中。 「春节十二响」由 $n$ 个子程序构成，第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树，其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。 由于内存紧张，电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 $S_1, S_2, \dots, S_k$，并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系，则他们可以被分配到同一个段中，反之则不能。换言之，当且仅当 $a$ 和 $b$ 在调用树上**不是祖先-后代关系**，$a$ 和 $b$ 可以被分配到同一个段中。 一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值，所有段大小的和不能超过系统的内存大小。 现在艾莉芬想要知道，电力控制芯片至少要有多少内存，才能保证春节十二响的正确运行。即：最少需要多大的内存，才能通过先**将内存分成若干个段**，再**把每个子程序分配到一个段中**，使得**每个段中分配的所有子程序之间不存在祖先-后代关系**。

从标准输入读入数据。 第一行包含一个正整数 $n$ 表示子程序的个数，其中 $n\le 2\times 10^5$。 第二行有 $n$ 个用空格隔开的正整数 $M_1, M_2, \dots, M_n$，$M_i$ 表示第 $i$ 个子程序所需的内存空间。 第三行有 $n-1$ 个用空格隔开的正整数 $f_2, f_3, \dots, f_n$，满足 $f_i<i$，表示第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。

输出到标准输出。 仅一个整数，表示最小的内存需求。

输入 #1

5
10 20 20 30 30
1 1 2 2

输出 #1