영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
A continent consists of N different city-states. Exactly N - 1 pairs of city-states are directly connected by a trade route, in such a way that it is possible to travel between all pairs of city-states along a sequence of trade routes.
After centuries of living in harmony and peace, there are now strong tensions between the largest city-state, Katen, and a rival kingdom, Kattago. Katen plans to quickly conquer the other city-states to unite them in their struggle against Kattago.
Katen is about to embark on its first campaign to conquer several city-states to form a union. The union must consist of a connected group of city-states and always includes Katen. This means that it should be possible to travel between every city-state in the union using the trade routes without visiting a city-state outside the union. To simplify their logistics during the campaign, they want the number of frontier states in the union to be as small as possible. A frontier state is a city-state that is directly connected to exactly one other city-state within the union. Katen, however, is never counted as a frontier state.
For each number of city-states 1, 2, …, N-1 that Katen can conquer during a campaign, can you calculate the minimum number of frontier states in the resulting union?
Input
The first line of input contains the integer N (2 ≤ N ≤ 100,000), the number of city-states on the continent.
The next N - 1 lines describe the trade routes. Let all city-states be numbered 0, 1, …, N - 1, where Katen is city-state 0. Each line contains two integers a and b (0 ≤ a, b < N, a ≠ b), the names of two city-states directly connected by a trade route.
Output
On a single line, print the smallest number of frontier states in a union with 1, 2, …, N - 1 conquered city-states.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 21 | All city-states, except Katen, are connected by at most 2 trade routes. |
| 2 | 28 | N ≤ 1000 |
| 3 | 51 | No additional constraints. |
Explanation of sample
In the first example, Katen can conquer, for example, city-states 1 and 3 in a campaign. Then, only city-state 3 is a frontier state, because city-state 1 is directly connected to both Katen and city-state 3. However, once all 3 city-states are conquered, both city-states 2 and 3 become frontier states.
예제
예제 1
4 0 1 0 2 1 3
1 1 2
예제 2
8 0 1 1 2 2 3 3 4 3 7 2 5 5 6
1 1 1 1 2 2 3