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

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

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

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

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

#4971 upload 67 done 11 how_to_reg 9

정기 모임 3 timer 1s memory 1024MB

#4971

정기 모임 3 1s 1024MB