Tree Depth Sum
A tree is given in the form of a parent array. The parent array p of size N has p[i] as the parent of node i. The root of the tree is node 0, and its parent is given as -1. The depth of the root (node 0) is 0. The depth of any other node i is the depth of its parent p[i] plus 1.
Given the parent array, compute the sum of the depths of all nodes in the tree. Each node contributes its depth to the total sum.
Input
The first line contains an integer N, the number of nodes in the tree (1 <= N <= 1000).
The second line contains N integers, where the i-th integer is p[i], the parent of node i. p[0] will be -1, and for i > 0, 0 <= p[i] < i.
Output
Print a single integer: the sum of the depths of all nodes in the tree.
Constraints
1 <= N <= 1000 -1 <= p[i] < i for i > 0, and p[0] == -1.
Example 1
5 -1 0 0 1 1
6
N=5. Node 0 (depth 0). Nodes 1, 2 (children of 0, depth 1). Nodes 3, 4 (children of 1, depth 2). Sum = 0 + 1 + 1 + 2 + 2 = 6.
Example 2
3 -1 0 1
3
N=3. Node 0 (depth 0). Node 1 (child of 0, depth 1). Node 2 (child of 1, depth 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