不知道我这个到底对不对，测试用例都过了但是感觉好像不像树形dp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1510;

int h[N], e[N], ne[N], idx;
int n;
int f[N];
int is_root_used[N];
int is_root[N];
int is_leaf[N];

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

void dfs(int u) {
    if (is_leaf[u] == 1) {
        f[u] = 0;
        is_root_used[u] = 0;
        return;
    }
    int flag = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u] += f[j];
        if (is_root_used[j] == 0) flag = 1;
    }
    is_root_used[u] = 0;
    if (flag) {
        f[u] += 1;
        is_root_used[u] = 1;
    }
}

void solve() {
    memset(h, -1, 4 * (n + 2));
    memset(is_root, 0, 4 * (n + 2));
    memset(f, 0, 4 * (n + 2));
    memset(is_leaf, 0, 4 * (n + 2));
    // memset(is_root_used, 0, 4 * (n + 2));
    idx = 0;
    char op[6];
    for (int i = 1; i <= n; i ++) {
        scanf("%s", op);
        int m = op[3] - '0';
        int v = op[0] - '0';
        if (m == 0) is_leaf[v] = 1;
        for (int j = 1; j <= m; j ++) {
            int _v;
            scanf("%d", &_v);
            is_root[_v] = -1;
            add(v, _v);
        }
    }
    int root = 0;
    for (int i = 0; i < n; i ++) {
        if (is_root[i] == 0) {
            root = i;
            break;
        }
    }
    dfs(root);
    printf("%d\n", f[root]);
}

int main() {
    while (scanf("%d", &n) != -1) {
        solve();
    }
    return 0;
}

因为是从HDU1054转过来的，所以就直接当有向边处理了。。。

f[i]表示以i为根节点的子树中最少选择多少个点，is_root_used[i]来同时标识最少方案中是否选择了i这个节点（这里我感觉会有问题，因为最优方案可能不唯一）