比较经典的老题
题目意思：给你一颗节点数为n的树，然后其中m个特殊点，再给你一个值d，问你在树中有多少个点到这m个点的距离都不大于d。
这题的写法有点像树的直径求法，先随便选择一个点（姑且设为点1）来遍历一遍树，存下所有点到点1的距离。然后在m个特殊点中找到距离点1最远的点a1.
然后以a1为初始点遍历一遍树，求每一个点到a1的距离，存在dp[i]中。并且再在m个点中找到到a1距离最大的点a2.最后再以a2为初始点遍历一遍树，求到每一个点到a2的距离dp1[i]。然后for遍历所有点，如果dp[i]和dp1[i]都不大于d，那么合法解+1；
这里可以做一个小证明，如果一个点k还能在m个特殊点中找到距离大于到a1和到a2距离的点s的话，那么点k到a1的距离加上点k到s的距离将大于k到a1加上k到a2，那么在第二次搜索中搜到的距离a1最远的点就不应该是a2而是s，所以不成立。由此反证得知。
具体代码如下：
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
bool pd[];
int dp[],dp1[];
int dd[];
vector<int> a[];
int bfs(int u)
{
memset(pd,false,sizeof(pd));
memset(dp,,sizeof(dp));
pd[u]=;
queue<int> q;
q.push(u);
while(q.size()!=)
{
int t=q.front();
q.pop();
for(int i=;i<a[t].size();i++)
{
int v=a[t][i];
if(pd[v]) continue;
//cout<<"w="<<w<<endl; pd[v]=;
dp[v]=dp[t]+;
q.push(v);
}
}
return ;
}
int bfs1(int u)
{
memset(pd,false,sizeof(pd));
memset(dp1,,sizeof(dp1));
pd[u]=;
queue<int> q;
q.push(u);
while(q.size()!=)
{
int t=q.front();
q.pop();
for(int i=;i<a[t].size();i++)
{
int v=a[t][i];
if(pd[v]) continue;
//cout<<"w="<<w<<endl; pd[v]=;
dp1[v]=dp1[t]+;
q.push(v);
}
}
return ;
}
int main()
{
int i,j,k,l,x,y,n,m,d;
scanf("%d%d%d",&n,&m,&d);
// cout<<n<<" "<<m<<" "<<d<<endl;
for(i=;i<m;i++) scanf("%d",&dd[i]);
for(i=;i<n-;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
bfs();
int lon=,a1=;
for(i=;i<m;i++)
if(dp[dd[i]]>lon)
{
lon=dp[dd[i]];
a1=dd[i];
}
//cout<<lon<<"｡｡"<<a1<<endl;
bfs(a1);
lon=;
for(i=;i<m;i++)
if(dp[dd[i]]>lon)
{
lon=dp[dd[i]];
a1=dd[i];
}
//cout<<lon<<"｡｡"<<a1<<endl;
int ans=;
bfs1(a1);
for(i=;i<=n;i++)
{
if(dp[i]<=d&&dp1[i]<=d) ans++;
}
//for(i=1;i<=n;i++) cout<<dp[i]<<" "<<dp1[i]<<endl;
printf("%d\n",ans);
}