P5290 [12-Province Joint Exam 2019] Twelve Firecrackers for the Spring Festival

“During Qingming, the rain falls in torrents; on the road, travelers are heartbroken.” In the year $2075$, there was no spring rain during Qingming. Under the cover of snow filling the sky, the only thing moving through the icy wasteland was a snow vehicle carrying humanity’s faint hope. A journey of $4.22$ light-years ahead, for Earth, this lonely traveler, is probably extremely lonely too.

Only one hundred kilometers remain to Sulawesi, and the air inside the vehicle is even colder than outside the window. Four pairs of eyes stare at the screen in front of Elephant, which shows the key program that controls the planetary engine: Twelve Firecrackers for the Spring Festival. He needs to deploy it onto a chip in the power control system. “Twelve Firecrackers for the Spring Festival” consists of $n$ subprograms. The memory required by the $i$-th subprogram is $M_i$. The call relationships among these $n$ subprograms form a tree rooted at subprogram $1$, where the parent of subprogram $i$ in the call tree is subprogram $f_i$. Because memory is tight, the power-control chip provides a memory segmentation mechanism. You can divide memory into several segments $S_1$, $S_2$, ..., $S_k$, and pre-assign each program to a fixed segment. If two subprograms have neither a direct nor an indirect call relationship, then they can be assigned to the same segment; otherwise, they cannot. In other words, if and only if $a$ and $b$ are **not in an ancestor–descendant relationship** in the call tree, $a$ and $b$ may be assigned to the same segment. The size of a segment should be the maximum memory requirement among all subprograms assigned to that segment. The sum of the sizes of all segments must not exceed the total memory size of the system. Now Elephant wants to know the minimum memory the power-control chip must have to guarantee the correct running of Twelve Firecrackers for the Spring Festival. That is: what is the minimum memory needed such that, by first **dividing memory into several segments**, and then **assigning each subprogram to one segment so that no two subprograms within the same segment have an ancestor–descendant relationship**, the program can run correctly.

The first line contains a positive integer $n$ representing the number of subprograms, where $n \leqslant 2 \times 10^5$. The second line contains $n$ positive integers $M_1$, $M_2$, ..., $M_n$ separated by spaces, where $M_i$ denotes the memory required by the $i$-th subprogram. The third line contains $n - 1$ positive integers $f_2$, $f_3$, ..., $f_n$ separated by spaces, satisfying $f_i < i$, meaning that the parent of the $i$-th subprogram in the call tree is subprogram $f_i$.

Only one integer, representing the minimum required memory.

#### Explanation of Sample $1$. In the optimal plan, the memory is divided into three segments of sizes $10$, $20$, and $30$. Subprogram $1$ is assigned to the first segment, subprograms $2$ and $3$ are assigned to the second segment, and subprograms $4$ and $5$ are assigned to the third segment. It can be proven that no better plan exists. #### Subtasks  Note: In test points $10$, $11$, and $12$, subprogram $1$ is **not necessarily** an endpoint of the chain. Here, $M$ is the maximum memory requirement among all subprograms, i.e., $\max\left\{M_i\right\}$. For all data, $1 \leqslant n \leqslant2 \times 10^5$, $1 \leqslant M \leqslant 10^9$. After carefully reading the statement and analyzing the Constraints, Elephant begins to write a program to solve this problem. $\texttt{\$$$ login Elephant}$ $\texttt{password: ********}$ Elephant, senior programmer. The third engineering team of Yushi City reminds you: - There are a thousand rules for solving problems, but reading the statement is the first rule; - Non-standard coding leads to zero points and tears. $\texttt{\$$$ cd spring}$ $\texttt{\$$$ ac spring}$ $\texttt{Spring Accepted. Score: 100/100.}$ Translated by ChatGPT 5