树形覆盖问题的通用解法，距离可以任意替换，使用贪心思想

样例

#include <iostream>
#include <cstring>

using namespace std;

const int d = 2;
const int inf = 0x3f3f3f3f;
const int N = 1005;
int idx, h[N], e[2 * N], ne[2 * N];
int f[N][2]; //f[i][0]代表i节点到最近的消防站的距离，f[i][1]代表以i节点为根的子树中距离i节点最远的未控制节点.
int n, res;

void add (int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}


void dfs(int x, int fa) {//x为当前子树的根节点，fa代表当前节点的父节点
    f[x][0] = inf;
    f[x][1] = 0;
    for (int i = h[x]; ~i ; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, x);
        if (f[j][1] != -1) f[x][1] = max(f[x][1], f[j][1] + 1);//如果下面的节点没有被控制(即下面的节点没有被认定为必须成为消防站)，那么就用他的f[j][1]更新，即更新
        //父节点的最远未控制距离
        f[x][0] = min(f[x][0], f[j][0] + 1);//不管怎样都要更新最近消防站，因为我们是从下往上加走的
    }
    if (f[x][1] == d) {//如果有一个最远未控制节点距离未d那么当前这个点必须变成消防站了，因为树形结构的距离是确定的，我们从子树爬上来的。
        ++ res ;
        f[x][0] = 0;
        f[x][1] = -1;
    }
    if (f[x][1] + f[x][0] <= d) f[x][1] = -1;//可以理解为，如果当前节点的另一颗子树里面有一个节点能够覆盖当前这个最远未控制节点，那么就不用父节点去控制了。
    //相当于父节点的父节点也不需考虑父节点这颗子树了。
}

int main() {
    cin >> n ;
    memset(h, -1, sizeof h);
    for (int i = 2; i <= n ; i ++) {
        int b ;
        cin >> b ;
        add(i, b);
        add(b, i);
        // cout << b << " " << i << endl;
    }
    dfs(1, -1);
    if (f[1][1] != -1) ++res;
    cout << res << endl;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla