Khu vui chơi

Xem PDF



Tác giả:
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Ngoài việc học và thi, Nam cũng có dự định khi đến Hạ Long nhất định phải đi quần thể vui chơi giải trí nổi tiếng là Sun World Ha Long Park.

Sun World Ha Long Park có \(n\) trò chơi trong đó có \(m\) trò chơi mạo hiểm (\(m\le n\)). Mỗi trò chơi được bố trí ở một địa điểm và có \(n-1\) con đường, mỗi con đường nối chính xác hai địa điểm tổ chức trò chơi. Đảm bảo tất cả các địa điểm đều được kết nối bởi các con đường này. Mỗi con đường Nam mất một phút để đi qua nó.

Vì là người ưa mạo hiểm nên Nam chỉ chơi những trò mạo hiểm mà thôi, với lại, Nam không có nhiều thời gian nên Nam nhờ các bạn xác định tổng thời gian nhỏ nhất Nam đi trên các con đường để đến tất cả các điểm tổ chức trò chơi mạo hiểm.

Input

  • Dòng 1 chứa hai số nguyên \(n, m\) (\(2\le m\le n\le 10^5\))
  • Dòng 2 chứa \(m\) số nguyên khác nhau là số hiệu điểm tổ chức trò chơi mạo hiểm.
  • \(n-1\) dòng tiếp theo, mỗi dòng hai số nguyên \(a, b\) (\(0\le a,b\le n-1\)) mô tả một con đường nối điểm tổ chức trò chơi có số hiệu \(a\)\(b\).

Output

  • Đưa ra một số nguyên duy nhất là tổng thời gian ít nhất Nam đi qua các con đường để đến tất cả các điểm tổ chức trò chơi mạo hiểm.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(m=2\)\(n\le 100\)
  • Subtask \(2\) (\(30\%\) số điểm): \(m\le n\le 10^4\)
  • Subtask \(3\) (\(40\%\) số điểm): \(n\le 10^5\)

Example

Test 1

Input
7 2
5 0
4 0
3 1
0 6
0 1
2 1
5 2
Output
3

Bình luận