/*poj 1463 最小点覆盖 匈牙利*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 1510using namespace std;int n,num,head[maxn],match[maxn],c[maxn],ans;bool f[maxn];struct node{    int v,pre;}e[maxn*2];int init(){    int x=0;char s=getchar();    while(s<‘0‘||s>‘9‘)s=getchar();    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x;}void Clear(){    memset(c,0,sizeof(c));    memset(head,0,sizeof(head));    memset(match,0,sizeof(match));    num=ans=0;}void Add(int from,int to){    num++;e[num].v=to;    e[num].pre=head[from];    head[from]=num;}void Dfs(int now,int from,int dep){    c[now]=dep;    for(int i=head[now];i;i=e[i].pre){        int v=e[i].v;        if(v==from)continue;        Dfs(v,now,dep+1);    }}int dfs(int u){    for(int i=head[u];i;i=e[i].pre){        int v=e[i].v;        if(f[v])continue;f[v]=1;        if(match[v]==0||dfs(match[v])){            match[v]=u;return 1;        }    }    return 0;}int main(){    while(scanf("%d",&n)!=EOF){        int u,v,s;Clear();        for(int i=1;i<=n;i++){            u=init();s=init();            while(s--){                v=init();Add(u,v);Add(v,u);            }        }        Dfs(0,-1,0);        for(int i=0;i<n;i++)if(c[i]&1){            memset(f,0,sizeof(f));            ans+=dfs(i);        }        printf("%d\n",ans);    }    return 0;}

/*poj 1463 最小点覆盖 dp*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 1510using namespace std;int n,num,head[maxn],f[maxn][2];struct node{    int v,pre;}e[maxn*2];int init(){    int x=0;char s=getchar();    while(s<‘0‘||s>‘9‘)s=getchar();    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x;}void Add(int from,int to){    num++;e[num].v=to;    e[num].pre=head[from];    head[from]=num;}void Dfs(int x,int from){    int s=0;f[x][1]=1;    for(int i=head[x];i;i=e[i].pre){        int v=e[i].v;        if(v==from)continue;        Dfs(v,x);s++;        f[x][1]+=min(f[v][0],f[v][1]);        f[x][0]+=f[v][1];    }}int main(){    while(scanf("%d",&n)!=EOF){        int u,v,s;num=0;        memset(f,0,sizeof(f));        memset(head,0,sizeof(head));        for(int i=1;i<=n;i++){            u=init();s=init();            while(s--){                v=init();Add(u,v);Add(v,u);            }        }        Dfs(0,-1);        printf("%d\n",min(f[0][0],f[0][1]));    }    return 0;}

/*f[i][j][0/1] i子树走j步是否回到i的max*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 210using namespace std;int n,m,num,head[maxn],f[maxn][maxn][2],c[maxn],ans;struct node{    int v,pre;}e[maxn*2];void Add(int from,int to){    num++;e[num].v=to;    e[num].pre=head[from];    head[from]=num;}void Clear(){    num=0;ans=0;    memset(f,0,sizeof(f));    memset(head,0,sizeof(head));}void Dfs(int x,int from){    f[x][0][1]=c[x];    for(int i=head[x];i;i=e[i].pre){        int v=e[i].v;        if(v==from)continue;        Dfs(v,x);        for(int j=m;j>=0;j--)            for(int k=0;k<=j;k++){                if(j-k-1>=0)f[x][j][0]=max(f[x][j][0],f[x][j-k-1][1]+max(f[v][k][0],f[v][k][1]));                if(j-k-2>=0)f[x][j][0]=max(f[x][j][0],f[x][j-k-2][0]+f[v][k][1]);                //这里一开始漏掉了 可以先走v 也可以最后走v                 if(j-k-2>=0)f[x][j][1]=max(f[x][j][1],f[x][j-k-2][1]+f[v][k][1]);            }    }}int main(){    while(~scanf("%d%d",&n,&m)){        Clear();int u,v;        for(int i=1;i<=n;i++)            scanf("%d",&c[i]);        for(int i=1;i<n;i++){            scanf("%d%d",&u,&v);            Add(u,v);Add(v,u);        }        Dfs(1,-1);        for(int i=0;i<=m;i++){            ans=max(ans,f[1][i][0]);            ans=max(ans,f[1][i][1]);        }        printf("%d\n",ans);    }    return 0;}

/*poj 1947*/ #include<iostream>#include<cstdio>#include<cstring>#define maxn 210#define inf 0x3f3f3f3fusing namespace std;int n,p,num,head[maxn],root,f[maxn][maxn],l[maxn],r[maxn],fa[maxn],son[maxn][maxn],sum[maxn];struct node{    int v,pre;}e[maxn];void Add(int from,int to){    num++;e[num].v=to;    e[num].pre=head[from];    head[from]=num;}void Dfs(int now,int from){    fa[now]=from;    for(int i=head[now];i;i=e[i].pre){        int v=e[i].v;        if(v==from)continue;        son[now][++son[now][0]]=v;        Dfs(v,now);    }}int DP(int now){    if(!now)return 0;    int s=0;    for(int i=1;i<=son[now][0];i++)        s+=DP(son[now][i]);    sum[now]=s+1;    f[now][1]=son[now][0];    for(int i=1;i<=son[now][0];i++){        int x=son[now][i];        for(int j=sum[now];j>=1;j--)            for(int k=1;k<=sum[x]&&k<=j;k++)                f[now][j]=min(f[now][j],f[now][j-k]+f[x][k]-1);    }    return sum[now];}int main(){    scanf("%d%d",&n,&p);    int u,v;    for(int i=1;i<n;i++){        scanf("%d%d",&u,&v);        Add(u,v);Add(v,u);    }    Dfs(1,0);memset(f,127/3,sizeof(f));    sum[1]=DP(1);int ans=f[1][p];    for(int i=2;i<=n;i++)        ans=min(ans,f[i][p]+1);    printf("%d\n",ans);    return 0;}

/*poj 3342 树上最大独立集+方案数统计*/#include<iostream>#include<cstdio>#include<cstring>#include<map>#define maxn 210using namespace std;int n,num,head[maxn],f[maxn][2],g[maxn][2],cnt;map<string,int>r;struct node{    int v,pre;}e[maxn*2];void Add(int from,int to){    num++;e[num].v=to;    e[num].pre=head[from];    head[from]=num;}void Dfs(int x,int from){    g[x][0]=1;f[x][1]=1;g[x][1]=1;    int sum,mx;    for(int i=head[x];i;i=e[i].pre){        int v=e[i].v;        if(v==from)continue;Dfs(v,x);        mx=max(f[v][1],f[v][0]);sum=0;        if(mx==f[v][1])sum+=g[v][1];        if(mx==f[v][0])sum+=g[v][0];        f[x][0]+=mx;g[x][0]*=sum;        mx=f[v][0];sum=g[v][0];        f[x][1]+=mx;g[x][1]*=sum;    }}int main(){    while(1){        cin>>n;if(n==0)break;        cnt=0;num=0;r.clear();        memset(f,0,sizeof(f));        memset(g,0,sizeof(g));        memset(head,0,sizeof(head));            string u,v,root;        cin>>root;r[root]=++cnt;        for(int i=1;i<n;i++){            cin>>u>>v;            if(r[u]==0)r[u]=++cnt;            if(r[v]==0)r[v]=++cnt;            Add(r[u],r[v]);            Add(r[v],r[u]);        }        Dfs(r[root],0);        int mx,sum=0;        mx=max(f[r[root]][1],f[r[root]][0]);        if(mx==f[r[root]][1])sum+=g[r[root]][1];        if(mx==f[r[root]][0])sum+=g[r[root]][0];        printf("%d ",mx);        if(sum==1)printf("Yes\n");        else printf("No\n");    }}