树的k级覆盖问题

        给定一棵树，约定选定一个点，被选点可以覆盖与其距离不大于k的所有节点，问覆盖整棵树的最小选点数。
        上一篇《动态规划与状态设计》中提及了k=2的DP做法，但是随着k的增大，状态数也会随之增多，这里介绍一种贪心方法。

        贪心思路：选择树中最深的没有被覆盖的节点，标记其k级祖先，直到整棵树都被覆盖。
        具体实现时，要先确定树根，计算出每一个节点的深度，每次选最深的节点，判断其是否被覆盖。若无则标记k级祖先，否则继续选点。
        难点在于如何判断是否被标记。只需要开一个数组来记录每一个节点到与它最近的被标记点的距离即可。
        下面给出上一篇文章中的第一道题目(洛谷P2279，k=2)的示例代码。

#include <iostream>
#include <algorithm>

#define MAX 1001
#define inf 10000
using namespace std;
int n;
int father[MAX] = {0}, depth[MAX];//标记节点的父节点编号和深度,认为根节点为1号节点
int rk[MAX];//序号,用于深度排序
int dict[MAX];//离被标记点最近的距离

bool cmp(int a, int b) { return depth[b] < depth[a]; }//比较函数,用于深度排序

int main() {
    cin >> n;
    depth[1] = 1, rk[1] = 1, dict[0] = dict[1] = inf;//初始化,0是虚拟父节点
    for (int i = 2; i <= n; i++) {
        cin >> father[i];
        depth[i] = depth[father[i]] + 1, rk[i] = i, dict[i] = inf;//利用题目输入规则,直接确定深度和父节点
    }
    sort(rk + 1, rk + n + 1, cmp);//排序
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int f = father[rk[i]], gf = father[f];//获取父节点和祖父
        dict[rk[i]] = min(dict[rk[i]], min(dict[f] + 1, dict[gf] + 2));//更新距离
        if (dict[rk[i]] > 2) {//没被覆盖
            dict[gf] = 0, ans++;//标记父节点,计数器加一
            dict[father[gf]] = min(dict[father[gf]], 1), dict[father[father[gf]]] = min(dict[father[father[gf]]], 2);
            //更新祖父的父节点和祖父的距离
        }
    }
    cout << ans;
    return 0;
}

        标记祖父时，其所有子节点孙子节点都会在它们的距离更新中被发现已被覆盖，同时祖父的父节点和祖父节点也会更新距离，从而使兄弟节点也会得到覆盖。
        值得注意的是，如果一个节点没有父节点或者祖父节点，那么就用到了虚拟父节点的概念。当任何时候一个节点没有父节点或祖父节点时，都认为它是节点0。0就是虚拟父节点。这种方法是正确的，这是因为当一个节点未被覆盖但又没有父节点或祖父节点时，由于它是目前深度最深的未被标记的节点，只需标记根节点即可完成整棵树的全覆盖。标记0节点和标记根节点显然是等价的，它们都能覆盖整棵树，结果都是计数器加一。
        也就是说，标记虚拟父节点就是标记根节点，答案不变。所以不需要对没有父节点或祖父节点时特判。
        这个方法很普适，可以推广到k级半径的问题，不用存图。