377D

树形dp

就是求每个点到标记的点的最大距离 一个经典模型

有一个巧妙的方法，我们求出以这些关键点的直径，然后每个点到关键点的最大距离就是到直径两端的距离

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, d, root, ans, x;
int mark[N], d1[N], d2[N];
vector<int> G[N];
void dfs(int u, int last, int *d)
{
    for(int i = 0; i < G[u].size(); ++i)
    {
        int v = G[u][i];
        if(v == last) continue;
        d[v] = d[u] + 1;
        dfs(v, u, d);
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &d);    
    for(int i = 1; i <= m; ++i) scanf("%d", &x), mark[x] = 1;
    for(int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0, d1);
    for(int i = 1; i <= n; ++i) if(d1[i] > d1[root] && mark[i]) root = i;
    d1[root] = 0;
    dfs(root, 0, d1);
    root = 0;
    for(int i = 1; i <= n; ++i) if(d1[i] > d1[root] && mark[i]) root = i;
    dfs(root, 0, d2);
    for(int i = 1; i <= n; ++i) if(d1[i] <= d && d2[i] <= d) ++ans;
    cout << ans;
    return 0;
}