동굴

시간 제한3초메모리 제한256 MB

요약

n개 정점으로 이루어진 트리에서 같은 크기의 연결된 부분 k개로 나눌 수 있는 모든 k를 구한다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 정수론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

바이트아사르가 동굴 하나를 발견했다. 이 동굴은 $n$ 개의 방으로 이루어져 있으며, 통로들로 연결되어 있어 임의의 두 방 사이를 오가는 경로가 정확히 하나만 존재한다. 즉, 방과 통로는 하나의 트리를 이룬다.

바이트아사르와 친구들은 여러 그룹으로 나누어 동굴을 조사하려고 한다. 이때 다음 규칙을 지켜야 한다.

모든 그룹은 같은 개수의 방을 조사한다.
모든 방은 정확히 한 그룹에 의해 조사된다.
한 그룹에 배정된 방들은 서로 연결되어 있어야 한다. 즉, 어떤 그룹도 다른 그룹에 배정된 방을 거치지 않고 자신에게 배정된 모든 방 사이를 이동할 수 있어야 한다.

탐험가들을 나눌 수 있는 그룹의 개수 $k$ 로 가능한 값을 모두 구하여라.

입력

첫째 줄에 방의 개수를 나타내는 정수 $n$ ( $2 \le n \le 3 \times 10^{6}$ )이 주어진다. 방은 $1$ 번부터 $n$ 번까지 번호가 매겨져 있다.

다음 $n - 1$ 개의 줄에는 각각 하나의 통로가 주어진다. 이 중 $i$ 번째 줄 ( $1 \le i \le n - 1$ )에는 정수 $a_i$ ( $1 \le a_i \le i$ )가 주어지며, 이는 $i + 1$ 번 방과 $a_i$ 번 방을 잇는 통로가 있음을 의미한다.

출력

방들을 크기가 같은 $k$ 개의 그룹으로 나눌 수 있고 각 그룹의 방들이 서로 연결되도록 만들 수 있는 모든 정수 $k$ 를, 한 줄에 오름차순으로 공백 하나로 구분하여 출력한다.

힌트

예제3

예제 1
입력
```
6
1
2
3
3
5
```
예상 출력
```
1 3 6
```
예제 2
입력
```
2
1
```
예상 출력
```
1 2
```
예제 3
입력
```
5
1
2
3
4
```
예상 출력
```
1 5
```