Book of Evil

题目大意

就是给定一棵 个点的树🌲，有 个关键点
问你有多少个点满足到关键点的最大距离小于等于

分析

到关键点的最大距离无非就是，所以就可以分别跑两次 ，求子树内外的信息即可
然后所有的都可以直接初始化为无穷小，表示子树内/外不存在关键点
遇到关键点把距离设为 即可

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int dist[maxn][2], dis[maxn], cur;
int Head[maxn], Edge[maxn << 1], Next[maxn << 1];
bool vis[maxn];

inline void AddEdge(int u, int v) 
{
    Next[++cur] = Head[u];
    Head[u] = cur;
    Edge[cur] = v;
}

void dfs(int u, int f)
{
    if (vis[u]) dist[u][0] = dist[u][1] = 0;
    for (int i = Head[u]; i; i = Next[i]) {
        int v = Edge[i];
        if (v == f) continue;
        dfs(v, u);
        if (dist[v][0] + 1 > dist[u][0]) {
            dist[u][1] = dist[u][0];
            dist[u][0] = dist[v][0] + 1;
        } else {
            dist[u][1] = max(dist[v][0] + 1, dist[u][1]);
        }
    }
}

void sfd(int u, int f)
{
    for (int i = Head[u]; i; i = Next[i]) {
        int v = Edge[i];
        if (v == f) continue;
        if (dist[u][0] == dist[v][0] + 1) {
            dis[v] = max(dis[u] + 1, dist[u][1] + 1);
        } else {
            dis[v] = max(dis[u] + 1, dist[u][0] + 1);
        }
        sfd(v, u);
    }
}

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int main()
{
    memset (dis, 128, sizeof dis);
    memset (dist, 128, sizeof dist);
    int n = __read(), m = __read(), d = __read();
    while (m--) {
        int temp = __read();
        vis[temp] = 1;
    }

    for (int i = 1; i < n; ++i) {
        int u = __read(), v = __read();
        AddEdge(u, v), AddEdge(v, u);
    }

    dfs(1, 0), sfd(1, 0);

    int ans(dist[1][0] <= d);

    for (int i = 2; i <= n; ++i)
        if (dist[i][0] <= d && dis[i] <= d) ++ans;

    printf("%d\n", ans);
}