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.

Madoka and Ladder Decomposition | CodeChef Solution

Contents

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

Subtasks

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

Leave a Comment

Your email address will not be published.