30937번 - Do It Yourself? 다국어

문제

You are the head of a group of $n$ employees including you in a company. Each employee has an employee ID, which is an integer 1ドル$ through $n,ドル where your ID is 1ドル$. Employees are often called by their IDs for short: #1ドル,ドル #2ドル,ドル and so on. Every employee other than you has a unique immediate boss, whose ID is smaller than his/hers. A boss of an employee is transitively defined as follows.

• If an employee #$i$ is the immediate boss of an employee #$j,ドル then #$i$ is a boss of #$j$.
• If #$i$ is a boss of #$j$ and #$j$ is a boss of #$k,ドル then #$i$ is a boss of #$k$.

Every employee including you is initially assigned exactly one task. That task can be done by him/herself or by any one of his/her bosses. Each employee can do an arbitrary number of tasks, but doing many tasks makes the employee too tired. Formally, each employee #i has an individual fatigability constant $f_i,ドル and if #$i$ does $m$ tasks in total, then the fatigue level of #$i$ will become $f_i \times \text{m}^2$.

Your mission is to minimize the sum of fatigue levels of all the $n$ employees.

입력

The input consists of a single test case in the following format.

$n$

$b_2$ $b_3$ $\cdots$ $b_n$

$f_1$ $f_2$ $\cdots$ $f_n$

The integer $n$ in the first line is the number of employees, where 2ドル ≤ n ≤ 5 \times 10^5$. The second line has $n - 1$ integers $b_i$ (2ドル ≤ i ≤ n$), each of which represents the immediate boss of the employee #$i,ドル where 1ドル ≤ b_i < i$. The third line has $n$ integers $f_i$ (1ドル ≤ i ≤ n$), each of which is the fatigability constant of the employee #$i,ドル where 1ドル ≤ f_i ≤ 10^{12}$.

출력

Output the minimum possible sum of fatigue levels of all the $n$ employees.

제한

힌트

Figure J.1. Illustration of the three samples (from left to right)

The situations and solutions of the three samples are illustrated in Figure J.1.

For Sample Input 1, the unique optimal way is that each employee does his/her task by him/herself. That is, you should just say “Do it yourself!” to everyone.

For Sample Input 2, the unique optimal way is that the employee #1ドル$ does all the tasks. That is, you should just say “Leave it to me!” to everyone.

For Sample Input 3, one of the optimal ways is the following.

• #1ドル$ does the tasks of #1ドル$ and #2ドル,ドル and then the fatigue level of #1ドル$ will be 1ドル \times 2^2 = 4$.
• #2ドル$ does the task of #4ドル,ドル and then the fatigue level of #2ドル$ will be 2ドル \times 1^2 = 2$.
• #3ドル$ does the initially assigned task, and then the fatigue level of #3ドル$ will be 4ドル \times 1^2 = 4$.
• #4ドル$ does nothing, and then the fatigue level of #4ドル$ will be 8ドル × 0^2 = 0$.

Thus, the sum of the fatigue levels is 4ドル + 2 + 4 + 0 = 10$. There is another optimal way, in which the employees #1ドル,ドル #2ドル,ドル and #3ドル$ do their initially assigned tasks by themselves and #1ドル$ does the task of #4ドル$ in addition.