U525840 ¥邪恶之书
题目背景
给一棵树,树上有若干关键节点,计算有多少节点到所有关键节点的距离都不超过d?
题目描述
圣骑士在一片沼泽地中发现了古老的邪恶之书的踪迹。这片区域有 $n$ 个定居点。由于在沼泽中移动非常困难,因此人们踩出了 $n - 1$ 条小路。每条路径都连接着一个定居点,并且是双向的。人们还可以通过穿越小路,从任何一个定居点到达任何另一个定居点。
两个定居点之间的距离是指从一个定居点到达另一个定居点所需的最少路径数。圣骑士知道邪恶之书的伤害范围是 $d$ 。这意味着如果邪恶之书位于某个聚落中,那么它的伤害会影响到距离邪恶之书所在定居点 $d$ 或更小的其他定居点。
圣骑士听说有 $m$ 个定居点受到了邪恶之书的影响。它们的编号是 $p_1, p_2, ..., p_m$ 。请注意,圣骑士想要确定哪些定居点可能含有 "邪恶之书"。帮助他完成这项艰巨的任务吧。
输入格式
第一行输入三个整数 $n,m,d$ ( $1 ≤ n ≤ 2\times 10^5$ ) 。
第二行输入 $m$ 个整数 $p_1,p_2,\cdots ,p_m(1\le p_i\le n)$ ,表示受到影响的节点编号。
接下来的 $n-1$ 行分别包含两个整数: $u_i,v_i$ ( $1 \le u_i, v_i \le n$)描述一条树上的边。
输出格式
输出一个整数表示可能包含邪恶之书的定居点的数量
说明/提示
对于$30\%$ 的数据:$1\le n\le 2000,m=1$
对于$60\%$ 的数据:$1\le n\le 2000,1\le m\le n$
对于$100\%$ 的数据:$1\le n\le 2\times 10^5,1\le m\le n$