Madoka and Ladder Decomposition | CodeChef Solution

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 P_i ( 1 ≤ P_i ≤ i−1) be the parent of the vertex i.

Let’s define the depth array h as follows: h₁ = 1, and hi=h_Pi+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 P₂, . . . ,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⁵
• 1 ≤ P_i <i for all 2 ≤ i ≤ n
• The sum of n over all test cases is at most 8⋅10⁵

Subtasks

• Subtask 1 (10 points):
  • The sum of n is at most 2⋅103.
  • The time limit is 1 second.
• Subtask 2 (20 points):
  • h_i ≤ 3 for all i.
  • The sum of n is at most 105.
  • The time limit is 1 second.
• Subtask 3 (50 points):
  • The sum of n is at most 2⋅105.
  • The time limit is 1 second.
• 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.