Book of Evil（树dp）

题目：

给你一棵个结点的树。给个标记结点，距离。问树上有几个结点到所有标记结点的距离均。

做法：

考虑做一个树，表示结点到所有标记结点的最大距离。
求出之后，一遍看有多少就出结果了。
这个树怎么做呢？
先一遍求出以结点为根的子树下的标记到的最大距离，放到（若子树下无标记则为）。然后第二遍换根转移，每次用不经过儿子的，到子树下标记的最大距离更新。新开一个表示结点不经过第个儿子，到子树下标记的最大距离。则同时还要更新下结点的数组。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
vector<int> g[N], dp[N];
int mrk[N], f[N];
void dfs(int u, int p){
    f[u] = mrk[u] ? 0 : -inf;
    vector<int> vt;
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v != p){
            dfs(v, u); f[u] = max(f[u], f[v]+1);
            vt.push_back(f[v]+1);
        }else{
            vt.push_back(-inf);
        }
    }
    dp[u].resize(vt.size());
    for (int i = 0; i < vt.size(); ++i){
        if (g[u][i] != p) dp[u][i] = mrk[u] ? 0 : -inf;
        else dp[u][i] = -inf;
    }
    int pre = -inf;
    for (int i = 0; i < vt.size(); ++i){
        dp[u][i] = max(dp[u][i], pre);
        if (g[u][i] != p) pre = max(pre, vt[i]);
    }
    pre = -inf;
    for (int i = vt.size()-1; i >= 0; --i){
        dp[u][i] = max(dp[u][i], pre);
        if (g[u][i] != p) pre = max(pre, vt[i]);
    }
}
void dfs1(int u, int p){
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i]; if (v == p) continue;
        f[v] = max(f[v], dp[u][i]+1);
        for (int j = 0; j < dp[v].size(); ++j) dp[v][j] = max(dp[v][j], dp[u][i]+1);
        dfs1(v, u);
    }
}
int main(void){
    IOS;
    int n, m, d; cin >> n >> m >> d;
    for (int i = 0; i < m; ++i){
        int x; cin >> x; mrk[x] = 1;
    }
    for (int i = 0; i < n-1; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0); dfs1(1, 0);
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        //printf("%d ", f[i]);
        ans += (f[i] <= d);
    } 
    //printf("\n");
    cout << ans << endl;
    return 0;
}