Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python
Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".
Input:
- Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
- ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
- Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.
Output:
- Số đỉnh tốt.
Sample Test
Input:
6 2 3
1 5
2 3
3 4
4 5
5 6
1 2
Output:
3
Giải thích:
- 3 đỉnh tốt là đỉnh 3,4,5.
Ràng buộc
- Subtask 1: ~n <= 500.~ (50%)
- Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
- Subtask 3: Không giới hạn gì thêm. (20%).