1393 . 黑色騎士團的第二野望
TopCoder
Tags
Description
在第一次野望失敗，不久之後，黑色騎士團想出了新的對策。
他們佔據一個城市，使得這城市以及與之相連的城市，都在他的支配之下。
另外，這次他們學聰明了，為了使得支配容易，他們已經武力控制城市的對外連接方式
讓城市與城市之間只存在唯一的一條運輸途徑
你依舊要找出黑色騎士團最少需要攻佔多少座城市
並將結果報告回司令部，好讓司令部擬出對策，打破黑色騎士團的第二野望
Input Format
本題有多筆測試資料，請以EOF作為結束。(測試資料不超過十組)
第一行為一個數字，n，代表有幾個城市(1≦n≦10000)
接著有n-1行，每行兩個數字，st，ed分別代道路兩端連結的城市編號。
(1≦st，ed≦n)
Output Format
輸出黑色騎士團完成野望最小需要攻佔多少城市。
Sample Input 1
5
1 2
2 3
3 4
4 5
1 2
2 3
3 4
4 5
Sample Output 1
2
Hints
※2008/07/25 題目敘述修正 by akira，感謝 sa072686。
Problem Source
原TIOJ1393 / 快樂暑假營第三次練習比賽。
(Adapt from：minimum dominating set problem) Problem Setter：ggm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |