문제
정점이 N개인 트리가 주어진다. 각 정점은 1번부터 N번까지 차례대로 번호가 부여되어 있다. i번째 간선은 A_i번 정점과 B_i번 정점을 연결한다.
트리에서 정점 사이의 거리는 두 정점 사이에 존재하는 유일한 단순 경로에 포함되는 간선의 수로 정의한다.
사람들이 트리 위에서 모임을 개최하려 한다. 트리 위에서도 바이러스는 퍼지기 때문에 사람들은 정부의 방역 지침을 지켜가며 모임을 진행할 예정이다. 한 정점에 한 사람씩 참석해 거리두기를 유지하며 모이려고 한다.
정부가 X단계 방역 지침을 시행한다면 트리 위의 임의의 두 사람 사이의 거리는 X이상이 되어야 한다. 하지만 사람들은 너무 떨어져서 모임을 진행하고 싶지 않기에, 거리가 X를 초과하지도 않게 모이려고 한다. 따라서 트리에 있는 임의의 두 사람 사이의 거리가 정확히 X가 되도록 모일 것이다.
사람들은 최대한 모임을 크게 진행하고 싶기 때문에 앞서 설명된 거리의 조건을 지키며 트리에 수용할 수 있는 최대의 사람의 수를 구하려고 한다. 코로나 상황이 수시로 변하고 무슨 일이 일어날지 예측할 수 없기에 사람들은 여러 X의 가능성을 생각하고 있다. X = 1, ..., N의 모든 경우의 수에 대해 모일 수 있는 최대의 인원을 구해보자.
입력
첫 줄에 N이 주어진다. (1 <= N <= 200,000)
이후 N-1줄에 걸쳐 i번째 줄에 트리의 i번째 간선을 나타내는 A_i, B_i가 공백을 사이에 두고 주어진다.
(1 <= A_i, B_i <= N)
출력
N줄에 걸쳐 i번째 줄에는 방역 지침이 i단계일때 모일 수 있는 최대 인원을 출력하라.
예제
6
1 2
1 3
1 4
2 5
3 6
2
3
2
2
1
1
로그인해야 코드를 작성할 수 있어요.