树形dp常用代码模块

void dfs(int u){
    dp[u][0] = 0;dp[u][1] = 1;
    for(int i = h[u];~i;i = ne[i]){
        int k = v[i];
        dfs(k);
        dp[u][0] += dp[k][1];
        dp[u][1] += min(dp[k][0], dp[k][1]);
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1600, M = N * 2;

int h[N], v[M], ne[M], idx;
int dp[N][2];
bool st[N];
int n;

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

void dfs(int u){
    dp[u][0] = 0;dp[u][1] = 1;
    for(int i = h[u];~i;i = ne[i]){
        int k = v[i];
        dfs(k);
        dp[u][0] += dp[k][1];
        dp[u][1] += min(dp[k][0], dp[k][1]);
    }
}

int main(){
    while(cin >> n){
        memset(h, -1, sizeof h);
        idx = 0;
        memset(st, 0, sizeof st);
        for(int i = 0;i < n;++i){
            int id, cnt;
            scanf("%d:(%d)", &id, &cnt);
            for(int i = 0;i < cnt;++i){
                int t;cin >> t;
                add(id, t);
                st[t] = true;
            }
        }        
        int root = 0;
        while(st[root]) ++root;
        dfs(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
}