Tree Ancestor Sum
You are given a rooted tree represented by a parent array. The parent array P is such that P[i] is the parent of node i. The root node has parent -1. You are also given a value V[i] for each node i. For each node i, compute the sum of values V[j] for all nodes j that are ancestors of i (including i itself). Print these sums for all nodes from 0 to N-1 in order.
Input
The first line contains an integer N, the number of nodes. The second line contains N integers representing the parent array P, where P[i] is the parent of node i. The root has parent -1. The third line contains N integers representing the values V[i] for each node i.
Output
Print N integers, where the i-th integer is the sum of values of node i and all its ancestors.
Constraints
1 <= N <= 200000. -1 <= P[i] < i for all i != root. P[root] = -1. 0 <= V[i] <= 10^9.
Example 1
5 -1 0 0 1 1 10 20 30 40 50
10 30 40 70 80
Node 0 is root with value 10. Node 1 and 2 are children of 0. Node 3 and 4 are children of 1. Sums: Node 0: 10. Node 1: 10+20=30. Node 2: 10+30=40. Node 3: 10+20+40=70. Node 4: 10+20+50=80.
Example 2
3 -1 0 1 1 2 3
1 3 6
A line graph. Node 0: 1. Node 1: 1+2=3. Node 2: 1+2+3=6.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 -1 0 0 1 1 10 20 30 40 50
3 -1 0 1 1 2 3