Sum of Subtree Sizes
A tree is given as a parent array P, where P[i] is the parent of node i. The root node is 0, and its parent is given as -1. The tree has N nodes, labeled from 0 to N-1.
For each node u, its subtree consists of u itself and all its descendants. Calculate the size of the subtree rooted at each node u. The size of a subtree is the total number of nodes in it.
Print the sizes of the subtrees for nodes 0, 1, ..., N-1 in order, separated by spaces.
Input
The first line contains an integer N (the number of nodes).
The second line contains N integers, representing the parent array P. P[0] will always be -1. For i > 0, 0 <= P[i] < i.
Note: The condition P[i] < i guarantees that node i's parent always has a smaller index. This implicitly defines the tree structure and ensures no cycles, with node 0 as the root.
Output
Print N space-separated integers, where the $i$-th integer is the size of the subtree rooted at node i.
Constraints
1 <= N <= 1000
P[0] = -1
0 <= P[i] < i for 1 <= i < N
Example 1
5 -1 0 0 1 1
5 3 1 1 1
Tree: 0 -> {1, 2}, 1 -> {3, 4}. Sizes: Node 0: 5, Node 1: 3, Node 2: 1, Node 3: 1, Node 4: 1.
Example 2
3 -1 0 1
3 2 1
Tree: 0 -> 1, 1 -> 2 (a line graph). Sizes: Node 0: 3, Node 1: 2, Node 2: 1.
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