D. Book of Evil

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

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 p1, p2, …, pm. 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 p1, p2, …, pm (1 ≤ pi ≤ 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 ai and bi 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.

Examples
inputCopy
6 2 3
1 2
1 5
2 3
3 4
4 5
5 6
outputCopy
3
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.

题意：给我们一棵树，和一些特殊的点，问我们到这些特殊的点的距离都小于等于d的点有多少个。

我们可以用类似树的直径的思想来做。

我们先以1节点开始bfs找到最远的一个特殊点，在以找到的特殊点找到最远的另一个特殊点，这两个点对于这道题树的特殊点的直径。

然后判断每个点到这两个点的最远距离是否小于d即可，所以我们提前预处理出直径的两个点到所有点的距离即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,vis[N],p[N],dst,s1,s2,res,d1[N],d2[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
    to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
int bfs(int s){
    queue<pair<int,int> > q;   q.push({s,0});
    int id,mx=-1;   int st[N]={0}; st[s]=1;
    if(vis[s])  id=s,mx=0;
    while(q.size()){
        auto u=q.front();    q.pop();
        for(int i=head[u.first];i;i=nex[i]){
            if(!st[to[i]]){
                q.push({to[i],u.second+1});	st[to[i]]=1;
                if(vis[to[i]]&&u.second+1>mx)    id=to[i],mx=u.second+1;
            }
        }
    }
    return id;
}
void bfs1(int s,int *d){
    d[s]=1; queue<int> q;   q.push(s); 
    while(q.size()){
        int u=q.front();    q.pop();
        for(int i=head[u];i;i=nex[i]){
            if(!d[to[i]]){
                d[to[i]]=d[u]+1;    q.push(to[i]);
            }
        }
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&dst);
    for(int i=1;i<=m;i++)   scanf("%d",&p[i]),vis[p[i]]=1;
    for(int i=1;i<n;i++){
        int a,b;    scanf("%d %d",&a,&b);   add(a,b);   add(b,a);
    }
    s1=bfs(1);  s2=bfs(s1); bfs1(s1,d1);   bfs1(s2,d2);
    for(int i=1;i<=n;i++){
        if(max(d1[i],d2[i])-1<=dst) res++;
    }
    printf("%d\n",res);
    return 0;
}