Background

Wind, blowing through the deep winter of Plum Ridge; frost, like turbulent waves;
Snow, falling and burning everything to emptiness, like this elusive dream.
Waking up after many years, the copper rings on the palace gates have grown rust, and也开始生出离愁.

——银临《梅深不见冬》

Problem Description

Fusu walks out from the deep winter of Plum Ridge and arrives at a rooted tree with $n$ nodes.

If you are not familiar with trees, you can consider a tree as a simple undirected connected graph where the number of edges is exactly one less than the number of nodes.

If we designate node $x$ as the root of tree $T$, then the path from any node $y$ to the root is the set of nodes that $y$ traverses without repetition to reach $x$. It can be proven that such a set of nodes is unique.

A node $u$ is defined as a child of node $v$ if and only if $u$ is connected to $v$ and $u$ is not on the path from $v$ to the root. If $u$ is a child of $v$, then $v$ is defined as the parent node of $u$.

If I were like @_rqy (a genius but challenging individual), I might ask you how many labeled rooted trees with $n$ nodes exist where each node has no more than $k$ children. However, I don't know the answer to this question, so I won't ask you such a challenging problem.

Fusu starts at node $1$ of this tree with $n$ nodes, designated as the root. His movement rules are as follows: when Fusu is at node $u$, he can either choose an unvisited child node $v$ and move to $v$, or he can choose to return to the parent node of $u$.

Each node is assigned a weight $w$, where the weight of node $i$ is $w_i$. Fusu wants to place plum blossoms on some nodes of the tree. We stipulate that Fusu can place plum blossoms on node $u$ if and only if the following conditions are met:

Fusu is currently at node $u$.

For all children $v$ of $u$, node $v$ has been placed with $w_v$ plum blossoms.

Additionally, Fusu can retrieve plum blossoms from any node at any time without needing to be at that node.

Now, Fusu wants to know for each node, if he wants to place $w_i$ plum blossoms on node $i$, how many plum blossoms he needs to bring from Plum Ridge at a minimum.

Input Format

There is exactly one test case per input file.

The first line of the input is an integer $n$ representing the number of nodes in the tree.

The second line contains $n-1$ integers separated by spaces, where the $i$-th integer $p_i$ represents the parent node number of node $i+1$.

The third line contains $n$ integers separated by spaces, where the $i$-th integer represents $w_i$.

Output Format

Output one line with $n$ integers separated by spaces, where the $i$-th integer represents the number of plum blossoms needed to place $w_i$ on node $i$.

Sample Input and Output

Sample Input #1

3 
1 2 
1 1 1

Sample Output #1

2 2 1

Sample Input #2

3
1 1
1 1 1

Sample Output #2

3 1 1

Sample Input #3

6
1 1 2 3 4
3 14 1 5 12 15

Sample Output #3

21 20 13 20 12 15

Notes

Explanation of Sample Input and Output 1

In the input for Sample 1, each node requires one plum blossom.

If placing plum blossoms at node 1, Fusu moves from node 1 to node 2, then to node 3, places one plum blossom at node 3, returns to node 2, places one plum blossom at node 2, retrieves the plum blossom from node 3, and returns to node 1, placing the retrieved plum blossom at node 1. This requires two plum blossoms in total.

The scenarios for placing plum blossoms at nodes 2 and 3 are similar.

Explanation of Sample Input and Output 3

The input for Sample 3 is illustrated in the diagram.

Fusu first moves from node 1 to node 3, then to node 5, places 12 plum blossoms at node 5, returns to node 3, places 1 plum blossom at node 3, retrieves the 12 plum blossoms from node 5, and returns to node 1.

Then, he moves to node 2, through node 4 to node 6, places 15 plum blossoms at node 6, returns to node 4, places 5 plum blossoms at node 4. At this point, the tree has 21 plum blossoms: 5 at node 4, 15 at node 6, and 1 at node 3. He then retrieves the plum blossoms from node 6, returns to node 2, places 14 plum blossoms at node 2, retrieves the plum blossoms from node 4, returns to node 1, and places 3 plum blossoms at node 1, achieving the goal of placing plum blossoms at node 1.

The maximum cost is verified to be 21. The answers for other nodes are derived similarly.

Note that the answers for other nodes may not necessarily be obtained by following the movement path of that node.

Data Size and Constraints

• For test cases 5 and 6, there is a special property: each node has no more than 2 child nodes.
• For test cases 8 to 10, there is a special property: each node has no more than 5 child nodes.
• For test cases 11 to 14, there is a special property: the number of nodes on the path from any node to the root is no more than 3, i.e., the tree height is no more than 3.
• For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 10^5 + 4$, $1 \leq p_i \leq i$, and $1 \leq w_i \leq 1000$.

Hints

• The last digit of $n$ can help you quickly determine the special properties of the test case.

见题面 Input 部分

见题面 Output 部分