32147번 - Split the SSHS 4

문제

서울의 명소 서울과학고등학교는 1ドル$부터 $N$까지의 번호가 매겨진 정점이 $N - 1$ 개의 간선으로 연결된 구조를 가진다. 서울과학고등학교의 어떤 두 정점 사이도 몇 개의 간선만을 이용하여 오갈 수 있음이 보장된다. 즉, 서울과학고등학교는 트리이다.

성현이와 상훈이는 서울과학고등학교에서 다음과 같은 규칙의 게임을 하고 있다.

1. 상훈이는 리프이기 때문에, 서울과학고에 새로운 리프 노드를 추가하려고 한다. 이를 위해, 서울과학고의 임의의 정점에 새로운 정점을 간선으로 연결한다.
2. 성현이는 서울과학고의 정점들을 "터트린다".
   • 성현이는 한 번에 한 정점씩 터트릴 수 있다.
   • 어떤 정점 하나를 선택하여 터트리면, 그 정점으로부터의 거리가 1 이하인 정점들이 제거된다. 보다 자세히, 선택한 정점으로부터의 거리가 1 이하인 정점들과 그 정점들에 연결된 간선들이 전부 삭제된다. (어떤 두 정점 사이의 거리는 한 정점에서 다른 정점으로 이동할 때, 거쳐야 하는 최소 간선 개수이다.) 이 과정에서 서울과학고가 여러 개의 트리로 쪼개질 수도 있다.
   • 한 번 터지거나 제거된 정점은 다시 터트릴 수 없다.
   • 성현이는 이 과정을 학교 전체가 사라질 때까지 반복한다.

상훈이가 어디에 새로운 정점을 연결했을지 알 수 없기 때문에, 성현이는 가능한 모든 상황에 대비할 생각이다. 정점을 터트리는 것은 매우 힘이 들기 때문에 성현이는 최소 횟수로 작업을 끝내려고 한다. 상훈이가 1ドル$번, 2ドル$번, $\cdots,ドル $N$번 정점에 새로운 정점을 연결했을 때 성현이가 터트려야 할 최소 정점 수를 구해 보자.

단, 상훈이가 각 정점에 새로운 정점을 연결한 상황은 모두 독립적이라고 가정하자.

입력

첫 번째 줄에 $N$이 주어진다.

두 번째 줄부터 $N-1$개의 줄 중 $i$번째 줄에는 $i$번째 간선의 양 끝점을 나타내는 정수 $u_i,ドル $v_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점을 연결하는 간선이 있음을 나타낸다. (1ドル \leq i \leq N-1$)

출력

첫 번째 줄부터 $N$개의 줄 중 $i$번째 줄에 상훈이가 $i$번 정점에 새로운 정점을 연결한 상황에서 성현이가 터트려야 할 최소 정점 수를 출력하여라.

제한

• 1ドル \leq N \leq 300,000円$
• 1ドル \leq u_i, v_i \leq N$ (단, 1ドル \leq i \leq N-1$)

힌트