2215 . どーっちどっちの歌
TopCoder
Tags
Description
久違的Minecraft 直播，真的很久了...三個月?!
開始玩吧...先找我的家吧!
以上是百鬼綾目在唱出知名的「哪裡哪裡之歌」之前說的話。
回到正題! 一年比一年繁盛的Hololive JP 麥塊伺服器，也一年比一年容易迷路了! 這對總是記不起路的百鬼來說不是一件好事。這個伺服器有$n$棟編號為$1$到$n$的建築，其中有$n - 1$條雙向道路連接兩棟建築，而任兩棟建築都透過一系列的道路連接起來。一開始只有$1$號建築存在，接下來有$n - 1$次的擴建，第$i$次擴建會將編號$i+1$的建築與編號$p_{i+1}$的建築連接一條道路。
百鬼完全不知道她家在哪，所以她有可能從任何一棟建築開始，經過一些不重複的道路走到任何其他建築。現在你想要知道，在每一次擴建的時候，她在迷路的過程中最多可以經過多少條道路?
Input Format
輸入第一行有一個整數$n$，代表最後的建築數量。
接下來第二行有$n-1$個數字，第$i$個數字為$p_{i+1}$，代表第$i$次擴建連接$p_{i+1}$和$i+1$。
對於所有測資，$n \leq 10 ^ 5, \forall 2 \leq i \leq n, p_i < i$
Output Format
輸出$n - 1$行，代表每次擴建後百鬼最多可以經過多少條道路。
Sample Input 1
5
1 1 2 1
1 1 2 1
Sample Output 1
1
2
3
3
2
3
3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $n \leq 3000$ | 18 |
| 2 | 10~19 | 答案不會超過$150$ | 28 |
| 3 | 0~29 | 無其他限制 | 54 |