皇宫看守

https://loj.ac/problem/10157

不同于战略游戏要求每边有人看守，即只能靠自己或者靠儿子 https://www.cnblogs.com/qwq-/p/13569330.html

本题要求每个点有人看守，即对于点root可以靠自己靠儿子或靠父亲

设dp[root][0/1/2]表示0靠自己1靠爸爸2靠儿子

root靠自己可以从儿子的三种状态转移，但是要加上自己设看守的费用

root靠爸爸可以让儿子靠自己或者靠儿子的儿子（好爸爸）

注意这里！root靠儿子必须要有一个儿子靠自己，其余儿子靠自己或者靠儿子的儿子，实现见代码

特别的，根结点不能靠爸爸，叶子结点不能靠儿子

#include <bits/stdc++.h>
using namespace std;
int cnt[5000], dp[5000][10], son[5000][5000], k[5000], fa[5000];
void dfs(int root) {
    if (!cnt[root]) {
        dp[root][0] = k[root];
        dp[root][1] = 0;
        dp[root][2] = 0x3f3f3f3f;
        return;
    }
    for (int i = 1; i <= cnt[root]; i++) dfs(son[root][i]);
    dp[root][0] = k[root];
    int f = 0;
    for (int i = 1; i <= cnt[root]; i++) {
        dp[root][0] += min(dp[son[root][i]][1], min(dp[son[root][i]][0], dp[son[root][i]][2]));
        dp[root][1] += min(dp[son[root][i]][0], dp[son[root][i]][2]);
        dp[root][2] += min(dp[son[root][i]][0], dp[son[root][i]][2]);  // QAQ
        if (dp[son[root][i]][0] <= dp[son[root][i]][2])
            f = 1;
    }
    if (f == 0) {
        int minn = 0x3f3f3f3f;
        for (int i = 1; i <= cnt[root]; i++) {
            minn = min(minn, dp[son[root][i]][0] - dp[son[root][i]][2]);
        }
        dp[root][2] += minn;
    }
}
int main() {
    memset(dp, 0, sizeof(dp));
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        cin >> k[x] >> cnt[x];
        for (int j = 1; j <= cnt[x]; j++) {
            cin >> son[x][j];
            fa[son[x][j]] = x;
        }
    }
    for (int i = 1; i <= n; i++)
        if (!fa[i]) {
            dfs(i);
            cout << min(dp[i][0], dp[i][2]);
            break;
        }
    return 0;
}