TopCoder

Thumb maxresdefault
YenSean
Hello World!

User's AC Ratio

45.5% (5/11)

Submission's AC Ratio

33.3% (38/114)

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

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

Sample Output

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

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 5
For Testdata: 19 ~ 19, Score: 5
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 65536 262144
1 1500 65536 262144
2 1500 65536 262144
3 1500 65536 262144
4 1500 65536 262144
5 1500 65536 262144
6 1500 65536 262144
7 1500 65536 262144
8 1500 65536 262144
9 1500 65536 262144
10 1500 65536 262144
11 1500 65536 262144
12 1500 65536 262144
13 1500 65536 262144
14 1500 65536 262144
15 1500 65536 262144
16 1500 65536 262144
17 1500 65536 262144
18 1500 65536 262144
19 1500 65536 262144