UVa 10243

a tree dp problem, it's hard if you've never touched tree dp problem, but the idea blow the surface is the same with normal dp problem
state:
    dp[i][0], dp[i][1] - 0 means minimum exits without choosing node i, while 1 means minimum exits with choosing node i
transition:
    dp[i][0]+=dp[k][1]
    dp[i][1]+=min(dp[k][0], dp[k][1]), for all k is i's children
there are 2 tricky things here if you wanna do it bottom-up
1 need to initialize all leaf nodes to d[leaf][0]=0, d[leaf][1]=1, judge on if sizeof(l[leaf])==1 to see whether a node is a leaf
2 however you still need to do a recursive traversal on all nodes, to get the DAG order

/* UVas */
/*****************************************************************************/
int N, n, t;
int v[1001];
int d[1001][2];
vector<int> l[1001];
int dfs(int c, int p) {
    int &r=d[c][p];
    if (r!=-1) {
        return r;
    }
    v[c]=1;
    if (p) {
        r=1;
        for (int i=0; i<sz(l[c]); i++) {
            if (v[l[c][i]]) {
                continue;
            }
            r+=min(dfs(l[c][i], 0), dfs(l[c][i], 1));
        }
    } else {
        r=0;
        for (int i=0; i<sz(l[c]); i++) {
            if (v[l[c][i]]) {
                continue;
            }
            r+=dfs(l[c][i], 1);
        }
    }
    v[c]=0;
    return r;
}
int main(void) {
    while (cin>>N&&N) {
        for (int i=1; i<=N; i++) {
            cin>>n;
            l[i].clear();
            for (int j=0; j<n; j++) {
                cin>>t;
                l[i].pb(t);
            }
        }
        memset(d, -1, sizeof(d));
        cout<<max(1, min(dfs(1, 0), dfs(1, 1)))<<endl;
    }
    return 0;
}
/*****************************************************************************/