不取父亲结点，那么必须取儿子节点，这样才能保证父亲和儿子的连边会被覆盖； 取父亲结点，那么儿子节点可取 可不取； f [ u ] [ 0 ] += f [ v ] [ 1 ] ; f [ u ] [ 1 ] += min( f [ v ] [ 1 ] , f [ v ] [ 0 ] ) ;
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N=1e5+5; const int inf=0x3f3f3f3f; const int mod=1e7+7; const LL maxn=1e18; #define fi first #define se second #define ls (i<<1) #define rs ((i<<1)|1) LL read() { LL x=0,t=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); } while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return x*t; } struct edge { int from,to,next; edge(){} edge(int ff,int tt,int nn) { from=ff; to=tt; next=nn; } }; edge e[N<<1]; int f[N][2],head[N],tot; void init() { tot=0; memset(head,0,sizeof(head) ); } void add(int from,int to) { e[++tot]=edge(from,to,head[from] ); head[from]=tot; } void dfs(int u,int pre) { f[u][0]=0; f[u][1]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v==pre) continue; dfs(v,u); f[u][0]+=f[v][1]; f[u][1]+=min(f[v][1],f[v][0]); } } int main() { int n; while(scanf("%d",&n)!=EOF) { init(); for(int i=1;i<=n;i++) { int x,y; scanf("%d:(%d)",&x,&y); //printf("x=%d y=%d\n",x,y); while(y--) { int z=read(); add(z,x); add(x,z); } } dfs(0,-1); printf("%d\n",min(f[0][0],f[0][1] ) ); } return 0; }