比较经典的老题
题目意思：给你一颗节点数为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[100050]; int dp[100050],dp1[100050]; int dd[100050]; vector<int> a[100050]; int bfs(int u) { memset(pd,false,sizeof(pd)); memset(dp,0,sizeof(dp)); pd[u]=1; queue<int> q; q.push(u); while(q.size()!=0) { int t=q.front(); q.pop(); for(int i=0;i<a[t].size();i++) { int v=a[t][i]; if(pd[v]) continue; //cout<<"w="<<w<<endl; pd[v]=1; dp[v]=dp[t]+1; q.push(v); } } return 1; } int bfs1(int u) { memset(pd,false,sizeof(pd)); memset(dp1,0,sizeof(dp1)); pd[u]=1; queue<int> q; q.push(u); while(q.size()!=0) { int t=q.front(); q.pop(); for(int i=0;i<a[t].size();i++) { int v=a[t][i]; if(pd[v]) continue; //cout<<"w="<<w<<endl; pd[v]=1; dp1[v]=dp1[t]+1; q.push(v); } } return 1; } 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=0;i<m;i++) scanf("%d",&dd[i]); for(i=0;i<n-1;i++) { scanf("%d%d",&x,&y); a[x].push_back(y); a[y].push_back(x); } bfs(1); int lon=0,a1=1; for(i=0;i<m;i++) if(dp[dd[i]]>lon) { lon=dp[dd[i]]; a1=dd[i]; } //cout<<lon<<"｡｡"<<a1<<endl; bfs(a1); lon=0; for(i=0;i<m;i++) if(dp[dd[i]]>lon) { lon=dp[dd[i]]; a1=dd[i]; } //cout<<lon<<"｡｡"<<a1<<endl; int ans=0; bfs1(a1); for(i=1;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 ",ans); }