838 . 緊急避難所

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-exam2

Description

小王是快樂國的國王。快樂國總共有 $N$ 個城鎮（城鎮編號為 $1, 2, 3, \dots, N$），並且有 $N - 1$ 條雙向道路連接著這些城鎮。每個城鎮都可以藉由這 $N - 1$ 條雙向道路到達其他所有的城鎮，而每條雙向道路的長度都是一公里。

現在，小王決定在 $M$ 個城鎮設置緊急避難所，這些城鎮的編號為 $a_1, a_2, \dots, a_M$。而決定好這些緊急避難所的位置後，小王決定算出，對於每個城鎮，該城鎮抵達最近的緊急避難所需要的距離。假設第 $i$ 個城鎮到達最近的緊急避難所需要 $h_i$ 公里，小王希望算出 $\sum_{i = 1}^ {N} h_i$ 的值（也就是所有 $h_i$ 的總和），來當作評估市政的參考。

只要進入到設置有緊急避難所的城鎮，就算成功進入緊急避難所，而如果該城鎮本來就有設置緊急避難所的話，那該城鎮的 $h_i$ 值為 $0$。

注意到 $\sum_{i = 1}^ {N} h_i$ 這個數字有可能超過 int 整數儲存的範圍！

Input Format

輸入的第一行包含兩個正整數 $N, M$，分別代表快樂國的城鎮數量，以及緊急避難所的數量。

接下來的 $N - 1$ 行，每行包含兩個正整數 $u_i, v_i$，代表城鎮 $u_i$ 跟城鎮 $v_i$ 中間有一條長度為一公里的雙向道路連通。

接下來的一行，包含 $M$ 個正整數 $a_1, a_2, \dots, a_M$，代表有設置緊急避難所的城鎮編號。

  • $1 \leq N \leq 2 \times 10^ 5$
  • $1 \leq M \leq N$
  • $1 \leq u_i, v_i \leq N, u_i \neq v_i$
  • $1 \leq a_i \leq N$，保證所有 $a_i$ 都相異。
  • 保證任意城鎮都可以藉由雙向道路到達其他城鎮。

Output Format

輸出 $\sum_{i = 1}^ {N} h_i$ 於一行。

Sample Input 1

5 1
2 1
2 3
5 3
3 4
3

Sample Output 1

5

Sample Input 2

6 2
1 2
2 3
3 4
3 5
2 6
1 5

Sample Output 2

6

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~16 $M = 1, N \leq 1000$ 20
3 0~34 $M \leq 2$ 30
4 0~52 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3 4
1 1000 524288 65536 1 3 4
2 1000 524288 65536 2 3 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 2 3 4
10 1000 524288 65536 2 3 4
11 1000 524288 65536 2 3 4
12 1000 524288 65536 2 3 4
13 1000 524288 65536 2 3 4
14 1000 524288 65536 2 3 4
15 1000 524288 65536 2 3 4
16 1000 524288 65536 2 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 3 4
23 1000 524288 65536 3 4
24 1000 524288 65536 3 4
25 1000 524288 65536 3 4
26 1000 524288 65536 3 4
27 1000 524288 65536 3 4
28 1000 524288 65536 3 4
29 1000 524288 65536 3 4
30 1000 524288 65536 3 4
31 1000 524288 65536 3 4
32 1000 524288 65536 3 4
33 1000 524288 65536 3 4
34 1000 524288 65536 3 4
35 1000 524288 65536 4
36 1000 524288 65536 4
37 1000 524288 65536 4
38 1000 524288 65536 4
39 1000 524288 65536 4
40 1000 524288 65536 4
41 1000 524288 65536 4
42 1000 524288 65536 4
43 1000 524288 65536 4
44 1000 524288 65536 4
45 1000 524288 65536 4
46 1000 524288 65536 4
47 1000 524288 65536 4
48 1000 524288 65536 4
49 1000 524288 65536 4
50 1000 524288 65536 4
51 1000 524288 65536 4
52 1000 524288 65536 4
Submit
Back to Top