1243 . 感染 Infection
TopCoder
Tags
Description
一個國度裡，共n個城市的連通情形可以描述成一個tree
現在有若干個城市(c個)中爆發了嚴重的病毒，
被病毒感染的人都會瘋狂的寫ACM而無法停手，等到2000多題ACM全部寫完就會痛苦而死
不但如此，UVa Online Judge已經被頻率高達2473題/每秒的送題速率送到癱瘓，病情已經無法控制!!
而且更糟的是，病毒會沿著道路(tree上的邊)不斷由被感染的城市
擴散到相鄰的未被感染的城市，最後全世界都會陷入這個ACM的世紀大陰謀裡!
比較喜歡寫USACO的政府感覺到了事情的嚴重性，決定立刻做出應對，封鎖若干條道路(疫情也就無法通過這條道路傳播)
以防止疫情擴大，並希望至少能挽救k個城市中的人民
今給定這個國家的城市連接情形，以及疫情爆發的城市，和想挽救的城市數目k
試問: 至少要封鎖幾條道路才能達到目的?
Input Format
本題有多筆輸入。
第一行有三個整數n, k, i
n代表總共有幾個城市，k是希望至少能挽救k個城市中的人民，i則是已被感染的城市數量
第二行有i個整數，以空白分隔，代表被感染的城市序號 (城市編號由0~n-1)
接下來n-1行有2個整數，代表有道路相連的城市編號。
輸入給定的圖會是一棵tree
1 <= k <= n <= 1000
Output Format
請輸出一個整數，代表至少要封鎖幾條道路。
如果不可能，請輸出"ACM rules!" (不含雙引號)
Sample Input 1
17 12 3
2 14 12
0 3
3 2
2 4
2 1
0 5
5 6
5 15
5 16
16 14
16 12
14 7
7 8
7 10
7 11
10 9
10 13
2 14 12
0 3
3 2
2 4
2 1
0 5
5 6
5 15
5 16
16 14
16 12
14 7
7 8
7 10
7 11
10 9
10 13
Sample Output 1
4
Hints
可封鎖2-3, 14-16, 16-12, 14-7等四條道路。
※2008/03/03：範例輸入修正，感謝a123123123888。
※2015/04/07：Input Format修正，感謝a00012025(CBD)。
Problem Source
原TIOJ1243 / TIOJ例行賽IV, Problem Setter: kelvin
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 1 | 5 |
| 3 | 2 | 5 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 5 |
| 18 | 17 | 5 |
| 19 | 18 | 5 |
| 20 | 19 | 5 |