Two Centroids solution codeforces

Two Centroids solution codeforces

You are given a tree (an undirected connected acyclic graph) which initially only contains vertex 11. There will be several queries to the given tree. In the 𝑖-th query, vertex 𝑖+1�+1 will appear and be connected to vertex 𝑝𝑖�� (1𝑝𝑖𝑖1≤��≤�).

After each query, please find out the least number of operations required to make the current tree has two centroids. In one operation, you can add one vertex and one edge to the tree such that it remains a tree.

A vertex is called a centroid if its removal splits the tree into subtrees with at most 𝑛2⌊�2⌋ vertices each, with 𝑛 as the number of vertices of the tree. For example, the centroid of the following tree is 33 because the biggest subtree after removing the centroid has 22 vertices.

In the next tree, vertex 11 and 22 are both centroids.


Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1𝑡1041≤�≤104). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (2𝑛51052≤�≤5⋅105) — the number of nodes of the final tree.

The second line of each test case contains 𝑛1�−1 integers 𝑝1,𝑝2,,𝑝𝑛1�1,�2,…,��−1 (1𝑝𝑖𝑖1≤��≤�) — the index of the vertex that is connected to vertex 𝑖+1�+1.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 51055⋅105.


For each test case, output 𝑛1�−1 integers. The 𝑖-th integer is the answer to the 𝑖-th query — the least number of operations required to make the current tree have two centroids.

Two Centroids solution codeforces



1 1
1 2 3
1 2 3 2 5 2
1 2 2 4 5 5 7 8 9


0 1
0 1 0
0 1 0 1 2 3
0 1 2 1 0 1 0 1 2

The illustrations below are of the fourth example test case.

After the third query:

The tree already has vertices 22 and 33 as centroids, so no operations are needed.After the fourth query:

Adding vertex 𝑥 to the tree makes vertices 22 and 33 centroids. Only one operation is needed.After the fifth query:

Adding vertex 𝑥 and 𝑦 to the tree makes vertices 55 and 22 centroids. Two operations are needed.After the sixth query:

Adding vertex 𝑥𝑦, and 𝑧 to the tree makes vertices 55 and 22 centroids. Three operations are needed.

Leave a Reply

Your email address will not be published. Required fields are marked *