## 1428 - Tree Problem

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 312

Solved: 193

Description

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 = 6

Ans = 1

Ans = 2

Ans = 0

Ans = 0

Ans = 0

Ans = 0

Input

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, P, ……P[n]. (1 <= P[i] <= N)

It is guaranteed that the input data is a tree structure and has 1 as root.

Output

For each test case, output a line of N numbers in the following format:

Case #K: Ans Ans Ans …… Ans[N].

sample input
```2
7
1 1 3 2 1 3
4
1 2 3```
sample output
```Case #1: 6 1 2 0 0 0
Case #2: 3 2 1 0```
hint

source
© 2015 HUST ACMICPC TEAM. All Right Reserved.