题目链接： Codeforces 337 D Book of Evil 题意： 给一个 n 个节点和n−1条边的树，有 m 个给定的点，求这n个点中到这 m 个点的距离都小于等于d的点的个数？树上两点的距离就是树上两点间路径的边的数量。 数据范围： 1≤m≤n≤105,0≤d≤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; }