Codeforces 337 D Book of Evil(树形dp，两遍dfs)

题目链接：
Codeforces 337 D Book of Evil
题意：
给一个$n$个节点和$n-1$条边的树，有$m$个给定的点，求这$n$个点中到这$m$个点的距离都小于等于$d$的点的个数？树上两点的距离就是树上两点间路径的边的数量。
数据范围：$1\leq m \leq n \leq 10^5,0\leq d \leq n-1$。
分析：
需要一步转化。我们求每个点到这$m$个点的最远距离，只要最远距离大于$d$，那么这个点就是不可取的。这样子一来就很简单了，两遍$dfs$，记录距离最大值和次大值即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int n, m, d, total;
int head[MAX_N], id[MAX_N], flag[MAX_N];
int down[MAX_N], ddown[MAX_N];struct Edge {int v, next;
} edge[MAX_N * 2];void AddEdge(int u, int v)
{edge[total].v = v;edge[total].next = head[u];head[u] = total++;
}void init()
{total = 0;for (int i = 0; i <= n; ++i) {head[i] = -1;down[i] = ddown[i] = id[i] = flag[i] = 0;}
}void dfs_son(int u, int p)
{for (int i = head[u]; i != -1; i = edge[i].next) {int v = edge[i].v;if (v == p) continue;dfs_son(v, u);int son = down[v];if (flag[v] || down[v] > 0) son = down[v] + 1;if (son > down[u]) {ddown[u] = down[u];down[u] = son;id[u] = v;} else if (son > ddown[u]) {ddown[u] = son;}}
}void dfs_father(int u, int p)
{for (int i = head[u]; i != -1; i = edge[i].next) {int v = edge[i].v;if (v == p) continue;int father;if (id[u] != v) father = down[u];else father = ddown[u];if (flag[u] || father > 0) father++;if (father > down[v]) {ddown[v] = down[v];down[v] = father;id[v] = u;} else if (father > ddown[v]) {ddown[v] = father;}dfs_father(v, u);}
}int main()
{while (~scanf("%d%d%d", &n, &m, &d)) {init();for (int i = 0; i < m; ++i) {int u;scanf("%d", &u);flag[u] = 1;}for (int i = 1; i < n; ++i) {int u, v;scanf("%d%d", &u, &v);AddEdge(u, v);AddEdge(v, u);}dfs_son(1, 0);dfs_father(1, 0);int ans = n;for (int i = 1; i <= n; ++i) {if (down[i] > d) ans--;}printf("%d\n", ans);}return 0;
}