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

**Task**

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

**be the parent of the vertex i.**

*P*_{i }( 1 ≤*P*≤_{i}*i*−1)Let’s define the depth array* h* as follows:

**h**_{1}**= 1**, and

**for all**

*hi*=*h*_{Pi}+1**.**

*i*≥ 2The subtree of a vertex * u*, denoted

*, is defined as the set of vertices v such that the unique path from 1 to v contains u. Also, we define*

**S(u)****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
– the number of test cases. Then**T**test cases follow.**T** - The first line of each test case contains a single integer
– the size of the tree.**n** - The second line contains
integers*n*− 1.*P*_{2}, . . . ,P_{n}

**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⋅10^{5}**1 ≤****P**_{i}**<i**for all**2 ≤***i*≤*n*- The sum of
over all test cases is at most*n***8⋅10**^{5}

**Subtasks**

**Subtask 1 (10 points):**- The sum of
is at most*n***2⋅103**. - The time limit is
**1**second.

- The sum of
**Subtask 2 (20 points):**for all*h*≤ 3_{i}.**i**- The sum of
*n***105**. - The time limit is
**1**second.

**Subtask 3 (50 points):**- The sum of
is at most**n****2⋅105**. - The time limit is
**1**second.

- The sum of
**Subtask 4 (20 points):**- 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
```

**Solution – Madoka and Ladder Decomposition **

**C++**

**Python**

**Java**

**Disclaimer:** The above Problem **(Madoka and Ladder Decomposition)** is generated by **CodeChef** but the Solution is Provided by** CodingBroz**. This tutorial is only for **Educational **and **Learning** Purpose.