CodeForces 337D Book of Evil（双向dfs）

╰半夏微凉° 2022-06-06 03:57 119阅读 0赞

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.

Input

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.

Output

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.

Example

Input

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

Output

Note

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.

![9a60ac4ba370fac43671723a3417ebd9_v_1508977075][]

题解：

题意：

这题主要是理解题意比较难，给你n个节点，m个已经被感染了的节点，一个范围d，和n-1个边形成一颗树，让你求存在多少个点使得所有被感染的点与它的距离不大于d

思路：

将感染点中相距最远的两个点作为边界，当前点与那两个边界点的距离都小于d那么其他被感染的点也符合条件了，先从任意一个点dfs一遍树，求出距离最远的那个被感染了的点作为tar1，然后再从tar1 dfs一遍，求出最远的被感染的点作为tar2并将所有点与tar1的距离存在d1数组中，然后从tar2出发dfs一遍树求出所有点与tar2的距离存在d2数组中，然后遍历所有节点并计数符合d1\[i\]和d2\[i\]都小于d的点

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    int d1[100005];
    int d2[100005];
    int a[100005];
    vector<int>p[100005];
    int vis[100005];
    void dfs(int index,int deep,int b[])
    {
        b[index]=deep;
        for(int i=0;i<p[index].size();i++)
        {
            if(vis[p[index][i]])
                continue;
            vis[p[index][i]]=1;
            dfs(p[index][i],deep+1,b);
        }
    }
    int main()
    {
        int n,m,d,x,y,i,j,num,tar1,tar2;
        scanf("%d%d%d",&n,&m,&d);
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<n-1;i++)
        {
            scanf("%d%d",&x,&y);
            p[x].push_back(y);
            p[y].push_back(x);
        }
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        dfs(1,0,d1);
        tar1=a[0];
        for(i=1;i<m;i++)
        {
            if(d1[tar1]<d1[a[i]])
                tar1=a[i];
        }
        memset(vis,0,sizeof(vis));
        vis[tar1]=1;
        dfs(tar1,0,d1);
        tar2=a[0];
        for(i=1;i<m;i++)
        {
            if(d1[tar2]<d1[a[i]])
                tar2=a[i];
        }
        memset(vis,0,sizeof(vis));
        vis[tar2]=1;
        dfs(tar2,0,d2);
        num=0;
        for(i=1;i<=n;i++)
        {
            if(d1[i]<=d&&d2[i]<=d)
                num++;
        }
        printf("%d\n",num);
        return 0;
    }

[9a60ac4ba370fac43671723a3417ebd9_v_1508977075]: https://odzkskevi.qnssl.com/9a60ac4ba370fac43671723a3417ebd9?v=1508977075