| Codeforces Round 196 (Div. 1) |
|---|
| Закончено |
Паладин Манао напал на след древней Книги Зла в одной болотистой местности. Всего в этой местности расположено n населенных пунктов, пронумерованных числами от 1 до n. Из-за того, что передвигаться по местности очень сложно, люди вытоптали ровно n - 1 тропинок, каждая из которых соединяет некоторую пару населенных пунктов. По каждой из этих тропинок можно передвигаться в обоих направлениях. Из любого населенного пункта можно попасть в любой другой, перейдя по одной или нескольким тропинкам.
Назовем расстоянием между двумя населенными пунктами наименьшее количество тропинок, которые надо пересечь, чтобы попасть из одного пункта в другой. Манао известно, что у искомой им Книги Зла радиус действия d. Это означает, что если Книга Зла находится в некотором населенном пункте, то ее пагубное влияние (например, явление привидений и оборотней) распространяется в населенных пунктах на расстоянии d или меньше от него.
Манао услышал, что влияние Книги Зла было замечено в m населенных пунктах с номерами p1, p2, ..., pm. Заметим, что Книга возможно влияет и на другие населенные пункты, просто этого еще никто не заметил. Он хочет определить, в каких из населенных пунктов может находиться эта Книга. Помогите ему в этой непростой задаче.
В первой строке через пробел записано три целых числа n, m и d (1 ≤ m ≤ n ≤ 100000; 0 ≤ d ≤ n - 1). Во второй строке через пробел записано m различных целых чисел p1, p2, ..., pm (1 ≤ pi ≤ n). Далее следует n - 1 строка, каждая из которых описывает одну из тропинок, проложенных в рассматриваемой местности. Тропинка описывается парой разделенных пробелом чисел ai и bi, представляющих собой концы этой тропинки.
Выведите единственное число — количество населенных пунктов, в которых может находиться Книга Зла. Возможно, что информация, дошедшая до Манао, противоречива и не существует такого населенного пункта, где может находиться Книга. В таком случае выведите 0.
6 2 3
1 2
1 5
2 3
3 4
4 5
5 6
3
Пример 1. Радиус действия Книги Зла равен 3-ем, а ее воздействие было замечено в населенных пунктах 1 и 2. Таким образом, она может находиться в населенных пунктах под номерами 3, 4 и 5.
