| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 512 MB | 220 | 121 | 67 | 47.857% |
크기 N의 트리에서, 센트로이드란 정점을 기준으로 나누어지는 서브트리의 크기가 모두 N/2 이하인 정점을 뜻한다. 어떠한 트리라도 센트로이드가 존재함이 알려져있다.
1번 정점이 트리의 루트이며, i번 정점의 부모는 pi이고, pi<i이다.
1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드를 구하여라.
첫 줄에 N이 주어진다. (2 ≤ N ≤ 5×105)
둘째 줄에 i = 2부터 i = N까지, pi가 공백으로 구분되어 주어진다. (1 ≤ pi < i)
1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드의 번호를 공백으로 구분하여 순서대로 출력한다. 여러가지의 답이 존재한다면 그 중 가장 작은 것을 출력한다.
5 1 2 3 4
1 1 2 2 3
5 1 2 1 4
1 1 2 1 1