Power Strip Supply Counting

At Litang University, the Injustice 5 ranking contest is underway. Many students brought their laptops to compete, but soon realized there was only one outlet in the contest hall. To solve this, they brought their own power strips.

In detail, there are \(n\) power strips, numbered from \(1\) to \(n\). The power strip \(1\) is directly connected to the sole outlet. For each \(i\) from \(2\) to \(n\), you are given an integer \(u_i\) (with \(u_i .

After setting up the strips, the students plugged their chargers into the sockets. The configuration is given by a sequence \(a_1, a_2, \dots, a_n\), where \(a_i\) represents the number of chargers plugged into the socket of power strip \(i\).

We say that power strip \(i\) supplies power to a charger if the electric current from the sole outlet to that charger passes through strip \(i\). Equivalently, if a charger is plugged into power strip \(j\) and power strip \(i\) lies on the unique path from the outlet (connected to strip \(1\)) to strip \(j\), then strip \(i\) supplies power to that charger.

Your task is to calculate, for each power strip, the total number of chargers it supplies power to. In other words, for each power strip \(i\), compute the sum of \(a_j\) over all power strips \(j\) in the subtree of \(i\) (including \(i\) itself).

Please note: The depicted daisy‐chain connection of power strips is used merely to set a contest background scenario and is not an endorsement of unsafe electrical practices. Always prioritize electrical safety in real life!

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 10^5\)), the number of power strips.

The second line contains \(n-1\) integers \(u_2, u_3, \dots, u_n\) where \(u_i < i\) for \(2 \le i \le n\). This indicates that power strip \(i\) is connected to power strip \(u_i\).

The third line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)), where \(a_i\) represents the number of chargers plugged into the socket of power strip \(i\).

outputFormat

Output a single line containing \(n\) integers. The \(i\)-th integer should be the total number of chargers that receive power via power strip \(i\) (i.e. the sum of \(a_j\) over all power strips \(j\) in the subtree rooted at \(i\)).

sample

3
1 1
2 3 4

9 3 4