学步园

题目大意：给你一棵树，n个节点，现在需要照亮所有的边，问你最少需要在节点上放几个士兵?

思路：最简单的树形DP了吧，设d[ i ][ j ] 把表示节点i，状态为j时的把以i为根节点的子树的边全部照亮的最小值，j==0表示i节点不放兵，1表示放兵，那么d[ i ][ 0 ] = SIGMA（d[ v ][ 1 ]），d[ i ][ 1 ] = SIGMA(min(d[ v ][ 0 ]，d[ v ][ 1 ]))，v为i的子节点。

就是输入有点坑，又要抠。。 = =

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1555 ;

struct Edge
{
    int t,next;
} edge[MAXN<<1];

int tot,head[MAXN];

void add_edge(int s,int t)
{
    edge[tot].t=t;
    edge[tot].next = head[s];
    head[s] = tot++;
}

int d[MAXN][3];

void dfs(int u,int fa)
{
    d[u][0] = 0;
    d[u][1] = 1;
    for(int e = head[u];e!=-1;e = edge[e].next)
    {
        int v = edge[e].t;
        if(v == fa) continue;
        dfs(v,u);
        d[u][0] += d[v][1];
        d[u][1] += min(d[v][0],d[v][1]);
    }
}

char str[111];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        tot=0;
        memset(head,-1,sizeof(head));
        for(int i = 0;i<n;i++)
        {
            scanf("%s",str);
            int flag = 0;
            int s,m;
            for(int j=0;str[j]!='\0';)
            {
                if(str[j]>='0'&&str[j]<='9')
                {
                    int tmp = str[j]-'0';
                    j++;
                    while(str[j]>='0'&&str[j]<='9')
                    {
                        tmp = tmp*10 + str[j]-'0';
                        j++;
                    }
                    //printf("tmp = %d\n",tmp);
                    if(flag==0)
                    {
                        s = tmp;
                        flag ++;
                    }
                    else if(flag==1)
                    {
                        m = tmp;
                    }
                }
                else j++;
            }
            //printf("s = %d.m = %d\n",s,m);
            int a;
            for(int j = 0;j<m;j++)
            {
                scanf("%d",&a);
                add_edge(s,a);
                add_edge(a,s);
            }
        }
        dfs(0,-1);
        printf("%d\n",min(d[0][0],d[0][1]));
    }
    return 0;
}