32144번 - 트리를 쓰는 트리 문제

문제

경기과학고는 작년 말에 크리스마스 트리를 설치했다. 설치한 트리 $T$는 정점이 $N$개로, 이 중 1ドル$번 정점이 루트이고 $i>1$이면 $i$번 정점의 부모는 $a_i$번 정점이다. $T$의 부분 트리는 $T$의 어떤 정점 $X$에 대해 $X$와 $X$의 모든 자손 정점, 그리고 이들을 잇는 간선으로 이루어진 트리이다. $T$의 지름은 $T$의 임의의 두 점 사이의 거리 중 가장 긴 것이다.

• 지호: 성현아, 크리스마스 트리야!
• 성현: 그렇네! 그런데, 저 트리 너무 작아 보이는 것 같아. 지름을 크게 할 수 있는 방법이 없을까?
• 지호: 음... $T$의 루트를 포함하지 않는 부분 트리 $T'$를 잡으면, $T'$와 그 외의 트리를 연결하는 간선은 하나밖에 없잖아?
• 성현: 그렇지, 트리는 간선 하나를 없애면 무조건 두 연결 요소로 분할되니까.
• 지호: 그 간선이 $T'$의 정점 $A$와 $A$의 부모 $B$를 잇는 간선일 때, $T'$에서 임의의 정점 $C$를 선택해 $A$와 $B$ 사이의 간선은 삭제하고 $B$와 $C$ 사이에 간선을 추가하는 거야!
• 성현: 오! 그렇게 하면 트리의 지름을 늘릴 수도 있겠구나!
• 지호: 그런데, 그렇게 해서 지름을 얼마나 키울 수 있을지는 모르겠어...
• 성현: 음, 루트가 아닌 모든 정점 $X$에 대해 $X$와 그 부모 사이 간선을 끊고 새로 추가할 때, 이렇게 하면 얻을 수 있는 트리의 최대 지름을 구할 수 있을 것 같은데?
• 지호: 아! 그러면 $O(N^2)$ 미만에 해결할 수 있을 것 같아!

어떻게 해결한다는 걸까? 여러분이 한번 풀어 보자.

입력

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 $N-1$개의 양의 정수 $a_2, a_3, \cdots, a_N$이 공백으로 구분되어 주어진다.

출력

$N-1$개 줄에 걸쳐, $i$번째 줄에 $i+1$번 정점을 루트로 갖는 부분 트리를 떼었다 붙여 얻을 수 있는 크리스마스 트리의 최대 지름을 출력한다.

제한

• 2ドル \leq N \leq 300,000円$
• 1ドル \leq a_i < i$ (2ドル \leq i \leq N$)

힌트

지호가 $O(N^2)$ 미만에 해결할 수 있을 것 같다고 이야기한 부분은, 엄밀히 하면 모든 정점에 대해 $o(N^2)$에 해결할 수 있다는 뜻이다.