TopCoder

Thumb 343jksfld
ltf0501
願與最重要之人能再次相會。

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

28.2% (11/39)

Description

  在第一次野望失敗,不久之後,黑色騎士團想出了新的對策。

  他們佔據一個城市,使得這城市以及與之相連的城市,都在他的支配之下。

  另外,這次他們學聰明了,為了使得支配容易,他們已經武力控制城市的對外連接方式

  讓城市與城市之間只存在唯一的一條運輸途徑

  你依舊要找出黑色騎士團最少需要攻佔多少座城市

  並將結果報告回司令部,好讓司令部擬出對策,打破黑色騎士團的第二野望

Input Format

本題有多筆測試資料,請以EOF作為結束。(測試資料不超過十組)

第一行為一個數字,n,代表有幾個城市(1≦n≦10000)

接著有n-1行,每行兩個數字,st,ed分別代道路兩端連結的城市編號。

(1≦st,ed≦n)

Output Format

輸出黑色騎士團完成野望最小需要攻佔多少城市。

Sample Input

5
1 2
2 3
3 4
4 5

Sample Output

2

Hints

※2008/07/25 題目敘述修正 by akira,感謝 sa072686。

Problem Source

原TIOJ1393 / 快樂暑假營第三次練習比賽。
(Adapt from:minimum dominating set problem) Problem Setter:ggm

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 3000 65536
1 3000 65536
2 3000 65536
3 3000 65536
4 3000 65536
5 3000 65536
6 3000 65536
7 3000 65536
8 3000 65536
9 3000 65536