시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB138413531.250%

문제

정점이 $N$개인 트리가 주어진다. 각 정점은 $1$번부터 $N$번까지 차례대로 번호가 부여되어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 연결한다.

트리에서 정점 사이의 거리는 두 정점 사이에 존재하는 유일한 단순 경로에 포함되는 간선의 수로 정의한다.

사람들이 트리 위에서 모임을 개최하려 한다. 트리 위에서도 바이러스는 퍼지기 때문에 사람들은 정부의 방역 지침을 지켜가며 모임을 진행할 예정이다. 한 정점에 한 사람씩 참석해 거리두기를 유지하며 모이려고 한다. 

정부가 $X$단계 방역 지침을 시행한다면 트리 위의 임의의 두 사람 사이의 거리는 $X$이상이 되어야 한다. 하지만 사람들은 너무 떨어져서 모임을 진행하고 싶지 않기에, 거리가 $X$를 초과하지도 않게 모이려고 한다. 따라서 트리에 있는 임의의 두 사람 사이의 거리가 정확히 $X$가 되도록 모일 것이다.

사람들은 최대한 모임을 크게 진행하고 싶기 때문에 앞서 설명된 거리의 조건을 지키며 트리에 수용할 수 있는 최대의 사람의 수를 구하려고 한다. 코로나 상황이 수시로 변하고 무슨 일이 일어날지 예측할 수 없기에 사람들은 여러 $X$의 가능성을 생각하고 있다. $X = 1, \cdots, N$의 모든 경우의 수에 대해 모일 수 있는 최대의 인원을 구해보자.

입력

첫 줄에 $N$이 주어진다. $(1 \le N \le 200,000)$ 이후 $N-1$줄에 걸쳐 $i$번째 줄에 트리의 $i$번째 간선을 나타내는 $A_i, B_i$가 공백을 사이에 두고 주어진다. $(1 \le A_i, B_i \le N)$

출력

$N$줄에 걸쳐 $i$번째 줄에는 방역 지침이 $i$단계일때 모일 수 있는 최대 인원을 출력하라.

예제 입력 1

6
1 2
1 3
1 4
2 5
3 6

예제 출력 1

2
3
2
2
1
1

출처

High School > 경기과학고등학교 > 나는코더다 2021 송년대회 G번