#include<stdio.h>
#include<string.h>
struct{int v,next;}edg[20016];
int s[10008],vis[10008],head[10008],n,e;
int Dfs(int u){
	int place=0,tmp,r=0;vis[u]=1;
	for(tmp=head[u];tmp!=-1;tmp=edg[tmp].next){
		if(vis[edg[tmp].v]) continue;
		r+=Dfs(edg[tmp].v);
		if(place==2) continue;
		if(s[edg[tmp].v]==0)place=2;
		if(s[edg[tmp].v]==2)place=1;
	}s[u]=place;//0表示当前节点未被子节点覆盖，1表被子节点覆盖，2表示
				//需要覆盖子节点。
	return r+(place>>1);//由增加的一个节点0来简化根节点的判断，即根节
						//点如果不需要覆盖子节点，又没有父节点将其覆盖
						//此种待殊情况。
}
int main(){int i,u,v;
	while(~scanf("%d",&n)){
		memset(s,0,sizeof(s));
		memset(vis,0,sizeof(vis));
		memset(head,-1,sizeof(head));e=0;
		for(i=1;i<n;i++){
			scanf("%d%d",&u,&v);
			edg[e].v=v;edg[e].next=head[u];head[u]=e++;
			edg[e].v=u;edg[e].next=head[v];head[v]=e++;
		}
		edg[e].v=1;edg[e].next=head[0];head[0]=e++;
		printf("%d\n",Dfs(0));
	}
	return 0;
}

• Re:贪心的代码 附数据～ (91) dooder_daodao 2011-07-23 21:12:17
  • Re:贪心的代码 附数据～ (137) ruirong92 2013-02-08 22:18:26
• Re:贪心的代码 附数据～ (26) tang123456 2013-11-01 13:27:27