Kill All Monsters

There is a rooted tree with n vertices, where the root is vertex 1. Each vertex i contains a monster with hit points hp_i. Normally, a monster in vertex i can be killed only after the monster in its direct parent has been killed. When a monster is killed normally, the power consumed equals

\( hp_i + \sum_{\substack{\text{child } j \text{ is alive}}} hp_j \)

Alternatively, Kotori may use a magic spell to kill any monster at 0 power cost without any restriction (i.e. even if its parent is still alive). However, each magic spell can be used only once.

For each m = 0, 1, 2, \ldots, n (where m is the number of available magic spells), determine the minimum total power needed to kill all the monsters.

inputFormat

The first line contains an integer n (1 \le n \le 200), the number of vertices.

The second line contains n integers hp₁, hp₂, \ldots, hp_n (1 \le hp_i \le 10⁹), representing the hit points of the monsters.

The next n - 1 lines each contain an integer p_i (1 \le p_i \le n) for i = 2, 3, \ldots, n, where p_i is the parent of vertex i.

outputFormat

Output n + 1 integers. The m^th integer (starting from m = 0) is the minimum total power needed if at most m magic spells are available.

sample

3
3 2 1
1
1

9 5 3 3