K半径最小覆盖问题。

某谷题解区有提出使用树型dp解决的，但是这里我们讨论另一种贪心的做法。

贪心策略很简单，对于当前最深节点，如果它不能被覆盖到，我们即在它的祖父节点设置一个消防局，这样可以使全局解不会更差。

将节点按照深度排序，逐次拓展次深节点，逐次更新当前节点及其祖父节点的最近消防局距离。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1001;

int n;
int d[MAXN]; // 深度
int fa[MAXN]; // 父亲
int o[MAXN]; // 最近消防站的距离
int b[MAXN]; // 标记节点号
int u, v, w;
int ans;

bool cmp(const int a, const int b) {
    return d[a] > d[b];
}

int main() {
    ios::sync_with_stdio(false);

    cin >> n;

    o[0]= MAXN;
    for ( int i = 1; i <= n; ++i ) {
        b[i] = i;
        o[i] = MAXN;
    }

    for ( int i = 2; i <= n; ++i ) {
        cin >> fa[i];
        d[i] = d[fa[i]] + 1;
    }

    sort(b + 1, b + 1 + n, cmp); // 按照距离由远到近排序

    for ( int i = 1; i <= n; ++i ) {
        u = b[i]; // 自己
        v = fa[u]; // 父亲
        w = fa[fa[u]]; // 祖父
        o[u] = min(o[u], min(o[v] + 1, o[w] + 2)); // 更新距离最近消防站

        if ( o[u] > 2 ) {
            o[w] = 0; // 如果距离最近消防站覆盖不到则在它祖父处设置消防站
            ++ans;
            o[fa[w]] = min(o[fa[w]], 1); // 更新祖父节点的父亲的o值
            o[fa[fa[w]]] = min(o[fa[fa[w]]], 2); // 更新祖父节点的祖父节点的o值
        }
    }

    cout << ans << endl;

    return 0;
}