시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 (언어별 추가 시간 없음) 512 MB 20 9 8 66.667%

문제

크기 N의 트리에서, 센트로이드란 정점을 기준으로 나누어지는 서브트리의 크기가 모두 N/2 이하인 정점을 뜻한다. 어떠한 트리라도 센트로이드가 존재함이 알려져있다.

1번 정점이 트리의 루트이며, i번 정점의 부모는 pi이고, pi<i이다.

1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드를 구하여라.

입력

첫 줄에 N이 주어진다. (2 ≤ N ≤ 5×105)

둘째 줄에 i = 2부터 i = N까지, pi가 공백으로 구분되어 주어진다. (1 ≤ p< i)

출력

1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드의 번호를 공백으로 구분하여 순서대로 출력한다. 여러가지의 답이 존재한다면 그 중 가장 작은 것을 출력한다.

예제 입력 1

5
1 2 3 4

예제 출력 1

1 1 2 2 3 

예제 입력 2

5
1 2 1 4

예제 출력 2

1 1 2 1 1 

출처