Time Limit: 10s
Memory Limit: 128MB
A tree structure is very special structure, there is exactly one path connecting each pair of nodes.
Now, given a tree structure, which has N nodes(conveniently labeled from 1 to N). And the root of the tree is always labeled with 1. You are to write a program to figure out that, for every node V in the tree, how many nodes there are in the sub-tree rooted by V and it’s label number is larger than the label number of V.
For the example above:
Ans[1] = 6
Ans[2] = 1
Ans[3] = 2
Ans[4] = 0
Ans[5] = 0
Ans[6] = 0
Ans[7] = 0
There are multiple cases.
The first line is an integer T representing the number of test cases.
The following T lines each line representing a test case. For each case there are exactly two lines:
The first line with a single integer N(1 <= N <= 50000), representing the size of tree.
The second line with N – 1 numbers: P[2], P[3], ……P[n]. (1 <= P[i] <= N)
It is guaranteed that the input data is a tree structure and has 1 as root.
For each test case, output a line of N numbers in the following format:
Case #K: Ans[1] Ans[2] Ans[3] …… Ans[N].
2 7 1 1 3 2 1 3 4 1 2 3
Case #1: 6 1 2 0 0 0 Case #2: 3 2 1 0