最大点独立集(选出最多的点 使得所有点都是独立的 没有相邻的)

最大点独立集
dp[u][0] 表示不选当前点的 最大值
dp[u][1] 表示选当前点的 最大值

leaf  :dp[u][0] = 0, dp[u][1] = val[u]

!leaf :dp[u][0] = sum{ max(dp[v][0], dp[v][1]); v = {son[u]} }
       dp[u][1] = sum{ dp[v][0] + val[u]; {v = son[u]} }

ans = max(dp[root][0], dp[root][1]);

最小点覆盖集(选出最少的点 覆盖所有边)

最小点覆盖集
dp[u][0] 表示不选当前点
dp[u][1] 表示选当前点

leaf  :dp[u][0] = 0, dp[u][1] = 1

!leaf :dp[u][0] = sum{ dp[v][1]; v = son[u] }
       dp[u][1] = sum{ min(dp[v][0], dp[v][1]); v = son[u] } + 1

ans = min(dp[root][1], dp[root][1]);

最小点支配集(选出最少的点 使得每个点要么被选 要么被它的相邻点支配)

最小点支配集
dp[u][0] 表示不选当前点
dp[u][1] 表示选当前点
但是会有一种情况就是当前点没选 那么它的儿子如果没选那它是被支配还是没有呢？
所以这样设计会表示不了全部状态

考虑加一维
dp[u][0] 表示选当前点
dp[u][1] 表示未选当前点 且被支配
dp[u][2] 表示未选当前点 未被支配

leaf  :dp[u][0] = 1, dp[u][1] = INF, dp[u][2] = 0

!leaf :dp[u][0] = sum{ min{dp[v][0], dp[v][1], dp[v][2]}; v = son[u] } + 1
       dp[u][1] = 
           至少有一个子树是选了它才会被支配
           定义一个 flag 标记一下如果有子树选过了那么就不用管
           如果没有选过子树 则需要枚举将哪一个 dp[v][1] 变为 dp[v][0]
           tmp = sum{ min(dp[v][0], dp[v][1]); v = son[u] };

           if(flag) dp[u][1] = tmp;
           else 枚举所有子树 dp[u][1] = min(tmp - dp[v][1] + dp[v][0], dp[u][1]);
       dp[u][2] = sum{ dp[v][1]; v = son[u] }
ans = min(dp[root][0], dp[root][1]); // dp[root][2] 不合法

皇宫看守

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define LL long long
using namespace std;

const int N = 1550, M = N << 1;

int n;
int cost[N];
int h[N], e[M], ne[M], idx;
bool st[N];
LL dp[N][3];

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

void dfs(int u){

    if(h[u] == -1){
        // cout << u << endl;
        dp[u][0] = cost[u], dp[u][1] = INF, dp[u][2] = 0;
        return ;
    }

    dp[u][0] += cost[u];
    int tmp = 0; bool flag = false;
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        dfs(j);
        dp[u][0] += min(dp[j][0], min(dp[j][1], dp[j][2]));
        dp[u][2] += dp[j][1];
        int t = min(dp[j][0], dp[j][1]);
        if(t == dp[j][0]) flag = true;
        tmp += t;
    }

    dp[u][1] = 1e9;
    if(!flag){
        for(int i = h[u];~i;i = ne[i]){
            int j = e[i];
            dp[u][1] = min(tmp - dp[j][1] + dp[j][0], dp[u][1]);
        }
    }else dp[u][1] = tmp;
}

int main(){

    scanf("%d", &n);
    memset(h, -1, sizeof h);

    for(int i = 1;i <= n;i ++ ){
        int id, k, m, ver;
        scanf("%d%d%d", &id, &k, &m);
        while(m -- ){
            scanf("%d", &ver);
            add(id, ver);
            st[ver] = true;
        }
        cost[id] = k;
    }

    int root = 1;
    while(st[root]) root ++ ;

    dfs(root);

    printf("%d", min(dp[root][0], dp[root][1]));

    return 0;
}