TopCoder

User's AC Ratio

75.0% (9/12)

Submission's AC Ratio

40.3% (25/62)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10