Big Company Seungbeom's

Interview

Time limit1sMemory limit512 MB

Summary
Given a rooted tree of employees, pick a matching of edges where each node touches at most one chosen edge, maximizing the sum of products of endpoint skill values.
Level

Medium7 of 10

Topics
Tree, Dynamic programming, DFS, Greedy
Solved
No attempts yet

Problem

Seungbeom Inc. is a multi-level marketing company where all N employees, including the boss Seungbeom, are salespeople. Every salesperson except Seungbeom is assigned exactly one mentor (sasu). If salesperson A is the sasu of B, then B is called the busasu of A.

Founded last year, Seungbeom Inc. posted large profits and grew into a big company. To grow further, the company plans to introduce a mentoring program. Seungbeom can pair two salespeople who are in a sasu-busasu relationship as each other's mentor and mentee, and in that case the two salespeople are said to be in a mentoring relationship. A salesperson can belong to at most one mentoring relationship. That is, a salesperson cannot be a mentor to several people, cannot be a mentee of several people, and cannot be both a mentor and a mentee. Of course, some employees may belong to no mentoring relationship.

Each mentoring relationship produces a synergy effect. Seungbeom has quantified every salesperson's skill and found that the synergy of a mentoring relationship equals the product of the mentor's skill and the mentee's skill. Seungbeom wants to form mentoring relationships so that the sum of synergies over all mentoring relationships is maximized.

The figure above shows an example of Seungbeom Inc.'s company structure and mentoring relationships. Each circle is a salesperson, and the number inside is that salesperson's skill. Arrows show sasu-busasu relationships. In this case the maximum possible sum of synergies is 5×7 + 4×3 + 3×3 + 4×5 + 3×1 = 79.

Input

The first line gives the number of salespeople N (2 ≤ N ≤ 200,000). The salespeople are numbered 1, 2, …, N, and Seungbeom is always number 1.

The second line gives the sasu of salespeople 2 through N, in order, separated by spaces.

The third line gives the integers A1, A2, …, AN (0 ≤ Ai ≤ 100) representing the skill of salesperson i, in order, separated by spaces.

Output

Print the maximum possible sum of synergies over all mentoring relationships on the first line. If no mentoring relationship can be formed, print 0.

Examples2

  1. Example 1

    Input
    3
1 2
1 2 3
    Expected output
    6

  2. Example 2

    Input
    12
1 1 1 2 2 6 7 3 4 10 4
5 7 3 4 4 2 4 3 3 3 1 5
    Expected output
    79