Cây con nhỏ nhất

View as PDF

Time limit: 1.0s , Memory limit: 256M , Points: 1

Cho cây T gồm n đỉnh được đánh số từ 1 đến n, mỗi đỉnh được tô màu đen hoặc trắng. Cho danh sách k đỉnh v_1,v_2,..,v_k được tô màu đen, các đỉnh còn lại được tô màu trắng.

Cây S được gọi là con của cây T nếu cây S thu được bằng cách xóa đi một vài đỉnh và cạnh của cây T. Kích thước của một cây được định nghĩa là số đỉnh cây đó. Bạn hãy xác định kích thước nhỏ nhất của cây con S chứa tất cả các đỉnh được tô màu đen.

Input

  • Dòng đầu tiên chứa hai số nguyên nk (1 \le k \le n \le 2 \times 10^5).
  • n-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên uv mô tả các cạnh của cây (1 \le u,v \le n).
  • Dòng cuối cùng chứa k số nguyên v_1,v_2,...,v_k (1 \le v_i \le n).
  • Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây hợp lệ.

Output

  • In ra kích thước nhỏ nhất của cây S thỏa mãn điều kiện.

Examples

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

Notes

Trong ví dụ đầu tiên, cây T và cây con S nhỏ nhất được mô tả như trong hình sau:

drawing

Comments