# Nikita and game

## 题意翻译

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

## 题目描述

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