15448번 - Vera and Engineering Buildings 다국어

There are N engineering buildings at the University of Waterloo numbered from 1 to N. For i ≥ 2, there is a two-way bridge from building i to building xi. Two buildings are called neighbours if there is a bridge between them.

Each building has a unique aesthetic value which can be any integer. It is difficult to determine the exact aesthetic value of a building, so Vera would like to find a nice building, one that has higher aesthetic value than all of its neighbours. It takes Vera t_i seconds to inspect building i and the bridges to all of its neighbours. After the inspection, for each neighbour j of building i, Vera will know which of building i or j has higher aesthetic value.

What is the minimum total seconds such that it is guaranteed that Vera can find a nice building in that time no matter what the aesthetic values are? Vera can decide which building to inspect next based on the results of previous inspections. Ignore the time needed to travel between buildings.

Line 1 contains integer N (2 ≤ N ≤ 16).

Line 2 contains N integers t₁, . . . , t_N (1 ≤ t_i ≤ 10⁸).

Line 3 contains N − 1 integers x₂, . . . , x_N (1 ≤ x_i < i).

Print one line with one integer, the minimum total seconds that guarantees a nice building can be found.

For the first example, inspecting buildings 1 and 3 guarantees a nice building will be found.

For the second example, one optimal strategy is to always inspect building 3 first.