#include<cstdio>
#include<cstdlib>
#include<cstring>
#define min(a,b) ((a)<(b)?(a):(b))

struct edge
{
    int link,next;
};

edge v[20048];
int n,son[10024],e=0,f[10024][3];
bool visit[10024];

void work(int x)
{
    visit[x]=1;
    f[x][0]=0;f[x][1]=1;f[x][2]=1;
    for (int i=son[x];i!=0;i=v[i].next)
    {
        int j=v[i].link;
        if (!visit[j])
        {
            work(j);
            f[x][0]=f[x][0]+f[j][1];
            f[x][2]=f[x][2]+min(f[j][0],f[j][1]);
        }
    }
    for (int i=son[x];i!=0;i=v[i].next)
    {
        int j=v[i].link;
        if (!visit[j])
        {
            f[x][1]=min(f[x][2],f[x][0]-f[j][1]+f[j][2]);
        }
    }
    visit[x]=0;
}   

int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[++e].link=y;v[e].next=son[x];son[x]=e;
        v[++e].link=x;v[e].next=son[y];son[y]=e;
    }
    memset(visit,0,sizeof(visit));
    work(1);
    printf("%d\n",f[1][1]);
    return 0;
}

求数据证实

• Re:求神牛帮助！这个代码为什么WA? (1095) yudingl2 2011-05-15 19:43:11