Tree Path Sum
You are given a tree structure represented by a parent array. The tree is rooted at node 0. The parent array p is of length N, where p[i] is the parent of node i. For the root node (node 0), p[0] is -1.
Each node i has a value equal to its node index i (i.e., node 0 has value 0, node 1 has value 1, ..., node N-1 has value N-1).
For each node i from 0 to N-1, calculate the sum of values of all nodes on the unique path from the root (node 0) to node i, inclusive. Print these sums for each node in increasing order of node index.
Input
The first line contains an integer N (2 <= N <= 1000), the number of nodes in the tree.
The second line contains N integers, the parent array p, where p[i] is the parent of node i (-1 for the root node 0).
Output
Print N integers, where the i-th integer (0-indexed) is the sum of values on the path from the root to node i.
Constraints
2 <= N <= 1000 -1 <= p[i] < i for 0 < i < N p[0] == -1
Example 1
5 -1 0 0 1 1
0 1 2 4 5
N=5. Parents: node 1's parent is 0, node 2's parent is 0, node 3's parent is 1, node 4's parent is 1. Path sums: node 0: 0. node 1: 0+1=1. node 2: 0+2=2. node 3: 0+1+3=4. node 4: 0+1+4=5.
Example 2
3 -1 0 1
0 1 3
N=3. A line graph: 0 -> 1 -> 2. Path sums: node 0: 0. node 1: 0+1=1. node 2: 0+1+2=3.
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
3 -1 0 1