Problem 邪恶古籍
题目大意
给出一些关键点，求这棵树上到最远关键点距离小于等于d的有多少个。
Solution
一个非常简单的树形dp。然而我被这道题给玩坏了。
在经过分析以后，我们发现只需要维护两个数组，
一个数组记录这个点的上面的最远关键点（父亲那一串）到这个点的距离；
另一个数组记录这个点的子树上的最远关键点到这个点的距离。
这个应该是正解，其实也和我的做法差不多，但是较好理解。
我的垃圾做法如下：
对于每一个节点，开三个值，path,pathp,pathn。
path表示其子树上最远关键点到这个点的距离，
pathp表示其子树上次远关键点到这个点的距离，且与最远关键点不在同一颗子树上。
pathn表示其最远关键点所在的子树。
首先第一次dfs可以求出来这三个值。
然后再一次dfs，这次dfs的时候，path就变成了全树上最远关键点到这个点的距离，也就是我们最终要求的答案。
从根节点开始扫，若父亲的pathn指的不是这个点，那么这个点的path值就变成了父亲的path值+1；
如果父亲的pathn指的就是这个点，那么我们的pathp就起了作用。若pathp的值小于这个点的path值，那么就更新path值。
当然在这个dfs的过程中，也要保证维护pathp的存在。
然后为了写这玩意儿我拉低了整题的AC率，所以强烈不推荐这个奇奇怪怪的方法。
而且我还不知道是不是正解，鬼知道cf的数据强不强。所以如果有错误的话请各位指出。
反正oj上我是A掉了。
那么，最后祝各位写题愉快。
反正这题我写的是很无语的。
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node{
int next,to;
}e[];
bool neko[];
int n,m,d,x,u,v,path[],h[],ans=,tot=;
int pathp[],pathn[];
void add(int u,int v){
e[++tot].to=u;e[tot].next=h[v];h[v]=tot;
e[++tot].to=v;e[tot].next=h[u];h[u]=tot;
}
void dfspath(int x,int last){
path[x]=-;pathp[x]=-;
for(int i=h[x];~i;i=e[i].next){
if(e[i].to!=last){
dfspath(e[i].to,x);
if(path[x]<path[e[i].to]+){
pathp[x]=path[x];
path[x]=path[e[i].to]+;
pathn[x]=e[i].to;
}else if(pathp[x]<path[e[i].to]+)pathp[x]=path[e[i].to]+;
}
}
if(neko[x]&&path[x]<-)path[x]=;
if(neko[x]&&pathp[x]<-)pathp[x]=;
}
void dpdfs(int x,int last){
if(~last)
if(pathn[last]==x){
if(pathp[last]+>path[x]){
pathp[x]=path[x];
path[x]=pathp[last]+;
pathn[x]=;
}else if(pathp[last]+>pathp[x])pathp[x]=pathp[last]+;
}else{
if(path[last]+>path[x]){
pathp[x]=path[x];
path[x]=path[last]+;
pathn[x]=;
}else if(path[last]+>pathp[x])
pathp[x]=path[last]+;
}
if(path[x]<=d)ans++;
for(int i=h[x];~i;i=e[i].next)
if(e[i].to!=last)dpdfs(e[i].to,x);
}
int main(){
// freopen("cf337d.in","r",stdin);
memset(h,-,sizeof(h));
scanf("%d%d%d",&n,&m,&d);
for(int i=;i<=m;i++)
scanf("%d",&x),neko[x]=;
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
dfspath(,);
dpdfs(,-);
printf("%d",ans);
}