CF1827D.Two Centroids
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree (an undirected connected acyclic graph) which initially only contains vertex 1 . There will be several queries to the given tree. In the i -th query, vertex i+1 will appear and be connected to vertex pi ( 1≤pi≤i ).
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 ⌊2n⌋ vertices each, with n as the number of vertices of the tree. For example, the centroid of the following tree is 3 because the biggest subtree after removing the centroid has 2 vertices.
In the next tree, vertex 1 and 2 are both centroids.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤104 ). The description of the test cases follows.
The first line of each test case contains a single integer n ( 2≤n≤5⋅105 ) — the number of nodes of the final tree.
The second line of each test case contains n−1 integers p1,p2,…,pn−1 ( 1≤pi≤i ) — the index of the vertex that is connected to vertex i+1 .
It is guaranteed that the sum of n over all test cases does not exceed 5⋅105 .
输出格式
For each test case, output n−1 integers. The i -th integer is the answer to the i -th query — the least number of operations required to make the current tree have two centroids.
We can show that an answer always exists.
输入输出样例
输入#1
5 2 1 3 1 1 4 1 2 3 7 1 2 3 2 5 2 10 1 2 2 4 5 5 7 8 9
输出#1
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:
The tree already has vertices 2 and 3 as centroids, so no operations are needed.After the fourth query:
Adding vertex x to the tree makes vertices 2 and 3 centroids. Only one operation is needed.After the fifth query:
Adding vertex x and y to the tree makes vertices 5 and 2 centroids. Two operations are needed.After the sixth query:
Adding vertex x , y , and z to the tree makes vertices 5 and 2 centroids. Three operations are needed.