Educational Tree Problem

Interview

Time limit1sMemory limit1024 MB

Summary

Given a rooted tree where each child's value is at most its parent's, find the maximum sum of a parent-closed vertex set for each size k from 1 to N.

Level: Medium4 of 10
Topics: Sorting, Tree, Greedy
Solved: No attempts yet

Problem

The tree has $N$ vertices. Each vertex is numbered from $1$ to $N$ with no duplicates, and vertex $1$ is the root of the tree.

For every integer $i$ with $2 \leq i \leq N$ , the parent of vertex $i$ is vertex $p_i$ .

Vertex $i$ has the integer $A_i$ written on it, and $A_i \leq A_{p_i}$ always holds. Choose some vertices to maximize the sum of the integers written on the chosen vertices. Every chosen vertex must be either vertex $1$ or have its parent also chosen.

Find the answer for each possible number of chosen vertices.

Input

The first line gives the integer $N$ . $(2 \leq N \leq 300\ 000)$

The second line gives the sequence $p_2, p_3, \cdots, p_N$ , separated by spaces. $(1 \leq p_i < i)$

The third line gives the sequence $A_1, A_2, \cdots, A_N$ , separated by spaces. $(1 \leq A_i \leq 10^9)$

Output

Print $N$ lines. On the $i$ -th line, print the answer when exactly $i$ vertices are chosen.

Examples1

Example 1
Input
```
4
1 1 2
4 4 3 1
```
Expected output
```
4
8
11
12
```