← 返回题目列表

Codeforces · 337/D

D. 邪恶之书

中文机器翻译题面 查看原题

圣骑士马瑙在沼泽地区发现了古代邪恶之书的踪迹。该区域包含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。

示例

输入 #1

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

输出 #1

3

注意

样本1。《邪恶之书》的伤害范围为3,其效果已在聚居地1和2中注意到。因此,它可以在聚居地3、4或5中。