Nikita and game

题意翻译

一棵树初始只有一个编号为 1 的根结点。 $n$ 次操作，每次新增一个点作为 $p_i$ 的子结点，询问更新后有多少点可以作为树直径的端点。 $n\le3\times10^5$。

题目描述

Nikita plays a new computer game. There are $ m $ levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class $ y_{i} $ (and $ y_{i} $ is called parent-class for this new class). Thus, the classes form a tree. Initially there is only one class with index $ 1 $ . Changing the class to its neighbour (child-class or parent-class) in the tree costs $ 1 $ coin. You can not change the class back. The cost of changing the class $ a $ to the class $ b $ is equal to the total cost of class changes on the path from $ a $ to $ b $ in the class tree. Suppose that at $ i $ -th level the maximum cost of changing one class to another is $ x $ . For each level output the number of classes such that for each of these classes there exists some other class $ y $ , and the distance from this class to $ y $ is exactly $ x $ .

输入输出格式

输入格式

First line contains one integer number $ m $ — number of queries ( $ 1<=m<=3·10^{5} $ ). Next $ m $ lines contain description of queries. $ i $ -th line ( $ 1<=i<=m $ ) describes the $ i $ -th level and contains an integer $ y_{i} $ — the index of the parent-class of class with index $ i+1 $ ( $ 1<=y_{i}<=i $ ).

输出格式

Suppose that at $ i $ -th level the maximum cost of changing one class to another is $ x $ . For each level output the number of classes such that for each of these classes there exists some other class $ y $ , and the distance from this class to $ y $ is exactly $ x $ .

输入输出样例

输入样例 #1

4
1
1
2
1

输出样例 #1

2
2
2
3

输入样例 #2

4
1
1
2
3

输出样例 #2

2
2
2
2