CF337D.Book of Evil

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains n settlements numbered from 1 to n. Moving through the swamp is very difficult, so people tramped exactly n - 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 d. 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 d or less from the settlement where the Book resides.

Manao has heard of m settlements affected by the Book of Evil. Their numbers are _p_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.

勇士马瑙在一片沼泽地区发现了古老《邪恶之书》的踪迹。该地区包含 nn 个编号为 11 至 nn 的定居点。由于在沼泽中穿行极为困难,人们仅修筑了恰好 n−1n-1 条道路。每条道路连接某一对定居点,且是双向通行的。此外,任意两个定居点之间均可通过一条或多条道路相互抵达。

两个定居点之间的距离定义为:从其中一个定居点到达另一个定居点所需经过的最少道路数。马瑙得知《邪恶之书》具有伤害范围 dd。这意味着:若《邪恶之书》位于某个定居点,则其造成的伤害(例如幽灵与狼人的出现)将波及所有与该定居点距离不超过 dd 的其他定居点。

马瑙已获悉有 mm 个定居点受到《邪恶之书》的影响,其编号分别为 p1, p2, …, pmp_1,\,p_2,\,\dots,\,p_m。注意,《邪恶之书》可能还影响了其他未被探测到的定居点。马瑙希望确定哪些定居点可能藏有《邪恶之书》。请帮助他完成这项艰巨的任务。

输入格式

The first line contains three space-separated integers n, m and d (1 ≤ m ≤ n ≤ 100000; 0 ≤ d ≤ n - 1). The second line contains m distinct space-separated integers _p_1, _p_2, ..., p__m (1 ≤ p__i ≤ n). Then n - 1 lines follow, each line describes a path made in the area. A path is described by a pair of space-separated integers a__i and b__i representing the ends of this path.

第一行包含三个用空格分隔的整数 nn、mm 和 dd(1 ≤ m ≤ n ≤ 1000001 ≤ m ≤ n ≤ 100000;0 ≤ d ≤ n − 10 ≤ d ≤ n - 1)。
第二行包含 mm 个互不相同的、用空格分隔的整数 p1, p2, ..., pmp_1,\,p_2,\,...,\,p_m(1 ≤ pi ≤ n1 ≤ p_i ≤ n)。
随后是 n − 1n - 1 行,每行描述该区域内的一条路径。每条路径由一对用空格分隔的整数 aia_i 和 bib_i 表示,分别代表该路径的两个端点。

输出格式

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.

输出一个整数——可能藏有《邪恶之书》的聚落数量。有可能曼奥收到了相互矛盾的信息,导致不存在任何可能藏有《邪恶之书》的聚落。此时,请输出 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.

样例 1:《邪恶之书》的伤害范围为 3,且其影响已在聚落 1 和 2 中被观测到。因此,它可能位于聚落 3、4 或 5 中。

输入解题思路,AI测评打分。不知道怎么写?

首页