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