/* 应该是一道最小点覆盖问题,可以拆点用二分图做 这里用树形DP来解决 对叶子结点i,显然:dp[i][0]=0,dp[i][1]=1 否则,dp[i][0]=sum(dp[j][1],j为i的孩子), dp[i][1]=sum(MIN(dp[j][0],dp[j][1])) */ #include <vector> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <cstring> #include <ctime> #include <string> using namespace std; const int N=1600; int n; struct Edge { int v,next; }edge[2*N]; int first[N],e; int DP[N][2]; void addedge(int u,int v) { edge[e].v=v;edge[e].next=first[u];first[u]=e++; edge[e].v=u;edge[e].next=first[v];first[v]=e++; } void init() { int x,num,y; e=0; for(int i=0;i<n;i++) { first[i]=-1; DP[i][0]=0; DP[i][1]=1; } for(int i=0;i<n;i++) { scanf("%d:(%d)",&x,&num); for(int j=0;j<num;j++) { scanf("%d",&y); addedge(x,y); } } } int dfs(int x,int fa) { int flag=1; for(int k=first[x];k!=-1;k=edge[k].next) { if(edge[k].v!=fa) { dfs(edge[k].v,x); DP[x][1]+=min(DP[edge[k].v][0],DP[edge[k].v][1]); DP[x][0]+=DP[edge[k].v][1]; flag=0; } } } void solve() { dfs(0,-1); cout<<min(DP[0][0],DP[0][1])<<endl; } int main() { while(scanf("%d",&n)!=EOF) { init(); solve(); } }