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.
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≤𝑛≤5⋅1052≤�≤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 5⋅1055⋅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
input
output
0 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:
