Hello coders, today we are going to solve Madoka and Ladder Decomposition CodeChef Solution whose Problem Code is LADCOMP.

Contents

Madoka was given a tree on her coming of age, and not a simple one, but a rooted tree of n vertices with a root at the vertex with the number 1.

For all i ≥ 2, let Pi ( 1 ≤ Pii−1) be the parent of the vertex i.

Let’s define the depth array h as follows: h1 = 1, and hi=hPi+1 for all i ≥ 2.

The subtree of a vertex u, denoted S(u), is defined as the set of vertices v such that the unique path from 1 to v contains u. Also, we define
valu=max{h(v):v∈S(u)}.
A tree is divided into paths by a ladder decomposition if each vertex is located on exactly one path, and each vertex u with at least one child lies in the same path as its child v with the maximum valv, and if there are several such vertices, then the vertex with the minimum number is selected.

Madoka defines the beauty of a tree in the following way. Let the ladder decomposition of the path lengths be L1, . . . ,Lk, then the beauty of the tree is L21+L22+⋯+L2k
For each i (1≤i≤n), your task is to calculate the beauty of the tree formed by the first i vertices.

## Input

• The first line contains an integer T – the number of test cases. Then T test cases follow.
• The first line of each test case contains a single integer n – the size of the tree.
• The second line contains n − 1 integers P2, . . . ,Pn.

## Output

For each test case, print in a separate line a single integer – the answer to the problem.

## Constraints

• 1 ≤ T ≤ 10
• 2 ≤ n ≤8⋅105
• 1 ≤ Pi <i for all 2 ≤ in
• The sum of n over all test cases is at most 8⋅105

• The sum of n is at most 2⋅103.
• The time limit is 1 second.
• hi ≤ 3 for all i.
• The sum of n is at most 105.
• The time limit is 1 second.
• The sum of n is at most 2⋅105.
• The time limit is 1 second.
• Original constraints.
• The time limit is 2.2 seconds.

Sample Input

``````2
6
1 2 1 4 3
12
1 2 1 4 4 6 2 8 5 6 11``````

Sample Output

``````0 1 4 4 5 10
0 1 4 4 5 5 10 10 13 14 14 21``````