1243 . 感染 Infection

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

53.8% (7/13)

Submission's AC Ratio

31.4% (38/121)

Tags

TIOJcon 2008-TIOJcon-4th

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∼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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10
10 1500 65536 262144 11
11 1500 65536 262144 12
12 1500 65536 262144 13
13 1500 65536 262144 14
14 1500 65536 262144 15
15 1500 65536 262144 16
16 1500 65536 262144 17
17 1500 65536 262144 18
18 1500 65536 262144 19
19 1500 65536 262144 20
Submit
Back to Top