#28527. Book of Evil

Book of Evil

题目描述

骑士 Manao 在一个沼泽地区发现了邪恶之书的踪迹。该地区有 nn 个定居点,编号从 1 到 nn。在沼泽中移动十分困难,因此人们共修建了恰好 n1n-1 条道路。每条道路连接一对定居点且为双向通行。此外,从任意一个定居点出发,总可以通过一条或多条道路到达其他任意定居点。

两个定居点之间的距离指的是从一个定居点到另一个定居点至少要经过的道路数量。Manao 已知邪恶之书的危害范围为 dd。也就是说,如果邪恶之书被放在某个定居点上,那么该书的影响(例如幽灵和狼人出现)会波及距离该定居点不超过 dd 的其他定居点。

Manao 听说有 mm 个定居点受到了邪恶之书的影响,编号为 p1,p2,,pmp_1, p_2, \ldots, p_m。需要注意的是,实际上邪恶之书可能还影响了其他定居点,只是目前尚未被发现。Manao 想要确定哪些定居点有可能藏有邪恶之书。请你帮助他完成这个艰巨的任务。

输入格式

第一行包含三个用空格分隔的整数 nnmmdd1mn1000001 \le m \le n \le 1000000dn10 \le d \le n-1)。
第二行包含 mm 个互不相同的用空格分隔的整数 p1,p2,,pmp_1, p_2, \ldots, p_m1pin1 \le p_i \le n)。
接下来的 n1n-1 行,每行描述一条道路,由两个用空格分隔的整数 aia_ibib_i 构成,表示这条道路连接了定居点 aia_ibib_i

输出格式

输出一个整数,表示有可能藏有邪恶之书的定居点数量。如果 Manao 收集的信息存在矛盾,导致没有任何一个定居点可能藏有邪恶之书,则输出 0。

6 2 3
1 2
1 5
2 3
3 4
4 5
5 6
3

说明/提示

样例 1:邪恶之书的危害范围为 3,其影响已在定居点 1 和 2 被发现。因此,书有可能在定居点 3、4 或 5。