「Bzoj 1217」「HNOI2003」消防局的设立 (贪心/树形DP)

BZOJ 1217
给你一棵树，上面可以放置一些点可以使距离其2的点染色，求最少放置点染色方案。

贪心做法：对于一个点，如果他的爷爷没有放置点，就放在爷爷上。因为这样可以最优，爷爷放点之后兼顾本节点、父亲节点、兄弟节点。

DP做法：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 2000 + 10;

struct node {
    int d, no;
    node () {d = 0;}
    bool operator < (const node &b) const {
        return d > b.d;
    }
}nd[MAXN];

int n, ans = 0, f[MAXN], whw[MAXN];//whw记录离其最近的点的距离

void clean() {
}
int solve() {
    clean();
    nd[1].no = 1, whw[1] = whw[0] = n, f[1] = 0;
    for (int i = 2; i <= n; i++) scanf("%d", &f[i]), nd[i].d = nd[f[i]].d + 1, nd[i].no = i, whw[i] = n;
    std::sort(nd + 1, nd + 1 + n);
    for (int i = 1; i <= n; i++) {
        int u = nd[i].no, v = f[u], w = f[f[u]];
        whw[u] = std::min(std::min(whw[v] + 1, whw[w] + 2), whw[u]);
        if (whw[u] > 2) ans++, whw[w] = 0, whw[f[w]] = std::min(whw[f[w]], 1), whw[f[f[w]]] = std::min(whw[f[f[w]]], 2);
    }
    printf("%d\n", ans);
    return 0;
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}