Tree Subtree Sums
You are given a tree structure represented by a parent array. The parent array p of size N has p[i] as the parent of node i. The root node has p[0] = -1. For each node u, calculate the sum of values of all nodes in the subtree rooted at u. The value of each node is its index (0-indexed).
Input
The first line contains an integer N. The second line contains N integers representing the parent array p, where p[i] is the parent of node i. p[0] is always -1 for the root.
Output
Print N integers, where the i-th integer is the sum of values of all nodes in the subtree rooted at node i.
Constraints
1 <= N <= 200000. The input represents a valid tree.
Example 1
5 -1 0 0 1 1
10 8 2 3 4
N=5, root is 0. Children of 0 are 1, 2. Children of 1 are 3, 4. Subtree sums: Node 0: {0,1,2,3,4}=10. Node 1: {1,3,4}=8. Node 2: {2}=2. Node 3: {3}=3. Node 4: {4}=4. Output: 10 8 2 3 4
Example 2
3 -1 0 1
3 3 2
N=3, root is 0. Child of 0 is 1. Child of 1 is 2. Subtree sums: Node 0: {0,1,2}=3. Node 1: {1,2}=3. Node 2: {2}=2. Output: 3 3 2
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