一道树形DP，注意是边覆盖而不是点覆盖。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=1505;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
/*f[i][0] no safe f[i][1] yes safe */
struct edge{int y,next;}a[N];int len,last[N];
inline void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
int f[N][2],deg[N];
void treedp(int x)
{
    f[x][0]=0;f[x][1]=1;
    bool bk=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        treedp(y);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][0],f[y][1]);
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        len=0;memset(last,0,sizeof(last));
        memset(deg,0,sizeof(deg));
        for(int i=1,x,l;i<=n;i++)
        {
            scanf("%d:(%d)",&x,&l);++x;
            for(int j=1,y;j<=l;j++)scanf("%d",&y),++y,ins(x,y),++deg[y];
        }
        int root=0;
        for(int i=1;i<=n;i++)if(!deg[i]){root=i;break;}
        treedp(root);
        printf("%d\n",min(f[root][0],f[root][1]));
    }
    return 0;
}