## Fast Heavy-Light Decomposition

View as PDF

Points: 10
Time limit: 2.0s
Java 4.0s
Memory limit: 256M

Author:
Problem type

On an unweighted tree, there are nodes and edges. The nodes are numbered from to . All nodes have a parent , except for the root node, for which is . All nodes are able to reach the root by repeatedly going up the parent of the current node.

Initially, all nodes have a value of . Perform the following operation on each node :

Add to the value of all nodes on the path from to the root, including and the root themselves.

Output the final values of all nodes.

#### Input Specification

The first line contains one number: .

The second line of input contains numbers, the -th number is . If is not , then node is the parent of node . If is , then the node is the root. It is guaranteed that there are no cycles and exactly one node is the root.

The third line of input contains numbers, the -th number is . This means you must add to the value of all nodes from to the root, inclusive.

#### Output Specification

Output lines, the -th line containing the value of node .

#### Sample Input

5
0 1 1 3 3
1 2 4 8 16

#### Sample Output

31
2
28
8
16

#### Explanation for Sample

The path to root for is just . So, should be incremented by = .

The path to root for is . So, and should be incremented by = .

The path to root for is . So, and should be incremented by = .

The path to root for is . So, , , and should be incremented by = .

The path to root for is . So, , , and should be incremented by = .

Adding it all together the values at nodes , , , , and are , , , , and , respectively.