DHBB 2017 - LHP - 11 - Phở

Xem dạng PDF

Gửi bài giải

Điểm: 0,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Jo là một blogger chuyên viết bài về ẩm thực. Hôm nay, cô ấy muốn thăm các nhà hàng Phở ở Nam Định để xem nhà hàng Phở nào ngon nhất.

Có ~n~ nhà hàng ở Nam Định, đánh số từ ~0~ đến ~n - 1~. Tuy nhiên, chỉ có ~m~ nhà hàng trong số chúng là bán Phở. Jo chọn một nhà hàng bất kì để bắt đầu tìm hiểu. Có ~n - 1~ con đường ở Nam Định, mỗi con đường nối chính xác hai nhà hàng. Đảm bảo tất cả các nhà hàng được kết nối bởi các con đường này. Mỗi con đường Jo mất 1 phút để đi qua nó. Trong khoa học máy tính, một mạng các con đường với cấu trúc như trên được gọi là một cây.

Yêu cầu: Xác định tổng thời gian nhỏ nhất để Jo đi trên các con đường để đến tất cả các nhà hàng Phở.

Input

  • Dòng 1 chứa hai số nguyên ~n~ và ~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 các nhà hàng Phở.
  • ~n - 1~ dòng tiếp theo, mỗi dòng hai số nguyên ~a~ và ~b~ (~0 \le a, b \le n - 1~) mô tả một con đường nối hai nhà hàng ~a~ và ~b~.

Output

  • Một số duy nhất là tổng thời gian ít nhất Jo đi qua các con đường để thăm hết ~m~ nhà hàng Phở.

Sample Input 1

8 2
5 2
0 1
0 2
2 3
4 3
6 1
1 5
7 3

Sample Output 1

3

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.