3729 - 城镇警局
Description

n 个城镇编号 1 到 n,中间有 n-1 条通道,长度都为 1 公里(这些通道把 n 个城镇连成一棵树)。
n 个城镇共用 k 个警局,每个警局可以管理 d 公里以内的城镇治安。给出 n 个城镇的连接情况以及 k 个警局所在的城镇,问有多少城镇没有被任何一家警局管理。
(样例中只有 4 号城镇没有被管理。)

Input

第 1 行:3 个数 n, k, d(2 <= n <= 10^5, 1 <= k <= 10^5, 0 <= d <= n-1)。
第 2 行:共 k 个数,表示警局在哪个城镇 p_i(1 <= p_i <= n)。
后面 n-1 行:每行两个数 u, v,表示城镇 u 和城镇 v 之间存在道路(1 <= u, v <= n)。

Output

输出共 1 行,对应没有被警局管理的城镇数量。

Examples

Input

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

Output

1
Hint

一个城镇被管理,当且仅当它到最近的警局的距离不超过 d。以全部 k 个警局为多源起点做一次 BFS,求出每个城镇到最近警局的距离 dist[],统计 dist[i] > d 的城镇数即为答案。复杂度 O(n)。

Source
51nod 2665
Tags
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1