原题直通车: codeforces 337D Book of Evil
题意：一棵n个结点的树上可能存在一个Evil，Evil危险范围为d，即当某个点与它的距离x<=d时，那么x是危险的。
现已知道有m个点是危险的，问那个Evil可能存的点有多少。
分析: 昨晚傻X地暴力提交，自然得到的是TLE。今天看一神的代码才突然明白……
跟以往的题一样，两个DFS就可求出答案。
第一个DFS搜出所有危险点，并求出枝干上的点到最远的危险点的距离。
第二次DFS再往回遍历。具体的参考代码。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=111111;
vector<int>Tree[maxn];
int deep[maxn];
int n,m,d,ans;
bool vis[maxn],vid[maxn];
void DFS(int cnt){
vis[cnt]=true;
deep[cnt]=-1;
if(vid[cnt]) deep[cnt]=0;
int len=Tree[cnt].size();
for(int i=0;i<len;++i){
int son=Tree[cnt][i];
if(vis[son]) continue;
DFS(son);
deep[cnt]=max(deep[cnt],deep[son]+(deep[son]==-1?0:1));
}
}
void DFS_DP(int cnt,int up){
if(up<=d&&deep[cnt]<=d) ans++;
vis[cnt]=true;
int len=Tree[cnt].size();
vector<int>P,S;
for(int i=0;i<len;++i) {
int son=Tree[cnt][i];
if(vis[son]) continue;
P.push_back(deep[son]==-1?-1:(deep[son]+2));//兄弟结点-->父亲结点-->自身,所以得+2步
S.push_back(son);
}
int ls=S.size();
if(ls==0) return;
vector<int>L(ls),R(ls);
int Max=-1; //下面两循环是为了求出所有兄弟结点的最大deep值。
for(int i=0;i<ls;++i){
L[i]=Max;
if(P[i]>Max) Max=P[i];
}
Max=-1;
for(int i=ls-1;i>=0;--i){
R[i]=Max;
if(P[i]>Max) Max=P[i];
}
for(int i=0;i<ls;++i){
int newup=(up==-1?-1:(up+1));
newup=max(newup,max(L[i],R[i]));
if(vid[cnt]&&newup<1) newup=1;
DFS_DP(S[i],newup);
}
}
int main(){
cin>>n>>m>>d;
for(int i=1;i<=m;++i){
int a; cin>>a; vid[a]=true;
}
for(int i=1;i<n;++i) {
int a,b; cin>>a>>b;
Tree[a].push_back(b);
Tree[b].push_back(a);
}
DFS(1);
memset(vis,false,sizeof(vis));
ans=0;
DFS_DP(1,-1);
cout<<ans<<endl;
return 0;
}