Root to Leaf Path Sum
You are given a tree represented by a parent array. The root of the tree is the node with parent -1. The value of each node is its index (0-indexed). Your task is to calculate the sum of values of all nodes along each path from the root to any leaf node. Print all such sums in increasing order.
Input
The first line contains a single integer N, the number of nodes in the tree (1 <= N <= 1000). The second line contains N integers representing the parent array, where the i-th integer is the parent of node i. The root node has parent -1. Node indices are 0 to N-1.
Output
Print all root-to-leaf path sums in increasing order, separated by spaces.
Constraints
1 <= N <= 1000
Example 1
5 -1 0 0 1 1
2 4 5
Tree: 0 is root, 1 and 2 are children of 0, 3 and 4 are children of 1. Paths: 0->1->3 (sum 0+1+3=4), 0->1->4 (sum 0+1+4=5), 0->2 (sum 0+2=2). Sorted sums: 2 4 5.
Example 2
3 -1 0 1
3
A line graph: 0->1->2. Only one root-to-leaf path: 0->1->2. Sum: 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