这个 dp 我倒是真的一开始没有思路。

有一棵树，你从根出发，每次选择一个子树内的叶子到达，然后最多往上跳 \(k\) 步，继续重复这个过程，最多到几个点。

阴间模拟赛做到的题。
前两题完全不会，看到就很崩溃。这题依然只想到一个暴力求 LCA 建边以后强联通分量缩点再跑拓扑的做法，而且还是 \(n^2\) 的。

正确的姿势是，每棵子树总有一个位置是要停下的。为了到其它的子树去，这个位置一定是在最浅的那个叶子。注意，这是对于一堆叶子的 LCA 为根的子树来说的，在一个点根的子树中可能并步满足这个“金科玉律”。
知道了这一点，就先把最小的叶子的深度记下来，记作 \(low_u\)。

至于 dp，状态当然是一个点为根的子树中最多可能到的个数啦。
那么考虑怎么合并两个答案。我们遍历一个点的每一个出边，找到它们的 \(low\)，处理完下面的点，你应该是在这个深度上的，那么就判断这个深度和当前的深度是否不超过 \(k\)，不超过的话就把下面的答案加到上面来。为避免重复，加上来后还得把下面的答案清空。
最后统计答案再 dfs 一遍，每个点把最大的儿子的答案加上当前的答案就可以了。

等等，这个做法看上去好像不太靠谱啊，怎么只管了子树里最浅的儿子呢。
我刚刚看这个做法的时候也感觉不太对。但是仔细模拟一下这个过程就可以发现，我们其实是把每个叶子的答案加到了能通过上上下下一级一级往上跳到达的地方，这个状态就代表了所有下面能到这个点的叶子数。
而枚举一个点的出边把 \(low_v - dep_u \le k\) 的答案都加到这里就相当于把互相能到达的加到了一起。所以这个做法是对的。

感觉这题还是很妙的！

#include <cstdio>
#include <vector>
const int N = 1000005, INF = 0x3f3f3f3f;
std::vector<int> g[N];
int n, k, size[N], low[N], dep[N];
bool leaf[N];
void dfs(int u, int d) {
    dep[u] = d, low[u] = INF;
    if (leaf[u]) low[u] = d, size[u] = 1;
    for (int i = 0; i < (signed)g[u].size(); i++) {
        int v = g[u][i];
        dfs(v, d+1);
        low[u] = std::min(low[u], low[v]);
        if (low[v] - dep[u] <= k) size[u] += size[v], size[v] = 0;
    }
}
int get(int u) {
    int an = 0;
    for (int i = 0; i < (signed)g[u].size(); i++) 
        an = std::max(an, get(g[u][i]));
    return an + size[u];
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) leaf[i] = 1;
    for (int i = 2, x; i <= n; i++) {
        scanf("%d", &x);
        g[x].push_back(i), leaf[x] = 0;
    }
    dfs(1, 0);
    printf("%d", get(1));
    return 0;
}