1243 . 感染 Infection
TopCoder
Tags
Description
一個國度裡，共 $n$ 個城市的連通情形可以描述成一個 tree
現在有若干個城市 ($c$ 個) 中爆發了嚴重的病毒，
被病毒感染的人都會瘋狂的寫 ACM 而無法停手，等到 2000 多題 ACM 全部寫完就會痛苦而死
不但如此，UVa Online Judge 已經被頻率高達 2473 題/每秒的送題速率送到癱瘓，病情已經無法控制!!
而且更糟的是，病毒會沿著道路 (tree 上的邊)不斷由被感染的城市
擴散到相鄰的未被感染的城市，最後全世界都會陷入這個 ACM 的世紀大陰謀裡!
比較喜歡寫 USACO 的政府感覺到了事情的嚴重性，決定立刻做出應對，封鎖若干條道路(疫情也就無法通過這條道路傳播)
以防止疫情擴大，並希望至少能挽救 $k$ 個城市中的人民
今給定這個國家的城市連接情形，以及疫情爆發的城市，和想挽救的城市數目 $k$
試問：至少要封鎖幾條道路才能達到目的?
Input Format
本題有多筆輸入。
第一行有三個整數 $n, k, c$
$n$ 代表總共有幾個城市，$k$ 是希望至少能挽救 $k$ 個城市中的人民，$c$ 則是已被感染的城市數量
第二行有 $c$ 個整數，以空白分隔，代表被感染的城市序號 (城市編號由 $0\sim n-1$)
接下來 $n-1$ 行有 $2$ 個整數，代表有道路相連的城市編號。
輸入給定的圖會是一棵 tree
$1\le k\le n\le 1000$
Output Format
請輸出一個整數，代表至少要封鎖幾條道路。
如果不可能，請輸出 "ACM rules!" (不含雙引號)
Sample Input 1
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
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 |