CF337D.Book of Evil

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains nn settlements numbered from 1 to nn . Moving through the swamp is very difficult, so people tramped exactly n1n-1 paths. Each of these paths connects some pair of settlements and is bidirectional. Moreover, it is possible to reach any settlement from any other one by traversing one or several paths.

The distance between two settlements is the minimum number of paths that have to be crossed to get from one settlement to the other one. Manao knows that the Book of Evil has got a damage range dd . This means that if the Book of Evil is located in some settlement, its damage (for example, emergence of ghosts and werewolves) affects other settlements at distance dd or less from the settlement where the Book resides.

Manao has heard of mm settlements affected by the Book of Evil. Their numbers are p1,p2,...,pmp_{1},p_{2},...,p_{m} . Note that the Book may be affecting other settlements as well, but this has not been detected yet. Manao wants to determine which settlements may contain the Book. Help him with this difficult task.

输入格式

The first line contains three space-separated integers nn , mm and dd ( 1<=m<=n<=100000; 0<=d<=n11<=m<=n<=100000; 0<=d<=n-1 ). The second line contains mm distinct space-separated integers p1,p2,...,pmp_{1},p_{2},...,p_{m} ( 1<=pi<=n1<=p_{i}<=n ). Then n1n-1 lines follow, each line describes a path made in the area. A path is described by a pair of space-separated integers aia_{i} and bib_{i} representing the ends of this path.

输出格式

Print a single number — the number of settlements that may contain the Book of Evil. It is possible that Manao received some controversial information and there is no settlement that may contain the Book. In such case, print 0.

输入输出样例

  • 输入#1

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

    输出#1

    3
    

说明/提示

Sample 1. The damage range of the Book of Evil equals 3 and its effects have been noticed in settlements 1 and 2. Thus, it can be in settlements 3, 4 or 5.

首页