洛谷 P2279 [HNOI2003] 消防局的设立

思路：

和“战略游戏”很像，但是状态明显变多了。

dp[i][0]代表i节点向上覆盖至i的父亲的父亲。

dp[i][1]代表i结点向上覆盖至i的父亲。

dp[i][2]代表i结点覆盖自身

dp[i][3]代表i结点向下覆盖自己的儿子。

dp[i][4]代表i结点向下覆盖自己的孙子。

状态方程大家可以看洛谷中的题解，这里不过多浪费时间了，给出一个参考代码，逻辑会稍微清晰一点。

代码有注释：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 2000
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
vector<int>vec[MAX];
int dp[MAX][5];//五个状态
void dfs(int u) {
    dp[u][0] = 1;//由于这个状态必须选择本身作为消防站，并且自己选中之后，其他儿子的状态不必要考虑，因为已经覆盖了祖先了。
    dp[u][3] = 0;
    dp[u][4] = 0;
    for (int i = 0; i < vec[u].size(); i++) {//遍历儿子结点
        int son = vec[u][i];
        dfs(son);
        dp[u][0] += dp[son][4];//其他儿子的状态，状态需要取4，因为是需要取最小值，其他状态覆盖过多会使消防站重复
        dp[u][3] += dp[son][2];//同理，因为是向下覆盖一个，所以儿子结点只需要覆盖自身就行了。
        dp[u][4] += dp[son][3];//向下覆盖到孙子，所以儿子只需要保证向下覆盖一个就行，往下递推。
    }
    if (vec[u].empty()) {
        dp[u][1] = dp[u][2] = 1;//当没有儿子的时候只能选择自身作为消防站。
    }
    else {//否则：
        dp[u][1] = dp[u][2] = inf;//为了在min使用的时候方便
        for (int i = 0; i < vec[u].size(); i++) {
            int son = vec[u][i];
            int f1 = dp[son][0];//向上覆盖一个结点，意味着至少一个儿子节点需要向上覆盖两个结点。
            int f2 = dp[son][1];//只覆盖自己，意味着至少一个儿子结点需要向上覆盖一个结点。
            for (int j = 0; j < vec[u].size(); j++) {//其他儿子没必要向上继续覆盖了，只需要一个就行。
                if (i == j)continue;//儿子重合就继续遍历别的儿子。
                int son_o = vec[u][j];//遍历其他儿子。
                f1 += dp[son_o][3];//由于选中了一个儿子向上覆盖了，其他儿子的状态无所谓，因为取最小值，所以状态最好是向下覆盖的
                f2 += dp[son_o][2];//同理
            }
            dp[u][1] = min(dp[u][1], f1);//选择当前数量与我们孩子选择之后的数量的最小值。
            dp[u][2] = min(dp[u][2], f2);
        }
    }
    for (int i = 1; i <= 4; i++) {
        dp[u][i] = min(dp[u][i], dp[u][i - 1]);//如果一个结点可以向上覆盖两个点，那么它就一定包含向上覆盖一个点的状态，所以需要从中选取最优状态，一直推下去。
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 2; i < n + 1; i++) {
        int x;
        cin >> x;
        vec[x].push_back(i);//没有双向构图，是因为这里的结点是相对确定的，小编号一定是在最上面的。
    }
    dfs(1);
    cout << dp[1][2] << endl;//最后我们选择覆盖自身的结点，因为我们覆盖之后都是最佳状态了，当然是保证本层能够覆盖完，并且当前结点就是根结点，没法向上覆盖。
    return 0;
}