트리를 쓰는 트리 문제

경기과학고는 작년 말에 크리스마스 트리를 설치했다. 설치한 트리 $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)$ 시간에 해결할 수 있다는 뜻이다.