$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：从根结点\ u\ 出发可以获得的价值，f[u][0]\ 表示不选当前点，f[u][1]\ 表示选择当前点$
  $属性：\min$

• $2. 状态转移$
  $不选当前点：f[u][0]\ +=f[j][1]$
  $选择当前点：f[u][1]\ +=\min(f[j][0],f[j][1])$

可参考： 没有上司的舞会

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1510;

int n;
int h[N],e[N],ne[N],idx;
int f[N][2];
bool st[N];

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

void dfs(int u)
{
    f[u][1]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        f[u][0]+=f[j][1]; //不选当前点，则儿子必选
        f[u][1]+=min(f[j][0],f[j][1]); //选择当前点，则儿子可选可不选
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        //多组数据初始化
        idx=0;
        memset(h,-1,sizeof h);
        memset(f,0,sizeof f);
        memset(st,0,sizeof st);

        for(int i=0;i<n;i++)
        {
            int id,cnt;
            scanf("%d:(%d)",&id,&cnt);
            while(cnt--)
            {
                int ver;
                cin>>ver;
                add(id,ver);
                st[ver]=true;
            }
        }

        //找到根结点
        int root=0;
        while(st[root]) root++; 

        dfs(root);

        cout<<min(f[root][0],f[root][1])<<endl;
    }

    return 0;
}