No.1

#include <stdio.h>
struct stct0{
	int v,next;
}edge[200010];
int mark[100010],headg[100010],edgeN,deg[100010],q[100010],tail;
void addedge(int u,int v){
    edge[edgeN].v=v;
    edge[edgeN].next=headg[u];
    headg[u]=edgeN++;
    deg[u]++;
	return;
}
int dfs(int pos){
	int i,rem;
	if(mark[pos]==1) return 0;
	//printf("##%d",pos+1);
	mark[pos]=1,deg[pos]--;
	//printf("   %d\n",deg[pos]);
	for(i=headg[pos];~i;i=edge[i].next) if(mark[edge[i].v]==0) if((--deg[edge[i].v])==1) q[tail++]=edge[i].v;
	for(i=headg[pos];~i;i=edge[i].next){
		if(mark[edge[i].v]==0&&(deg[pos]<=0||deg[edge[i].v]<=1)){
			dfs(edge[i].v);
			break;
		}
	}
	return 1;
}
main(){
	int n,i,tot,u,v,j;
	while(~scanf("%d",&n)){
	    for(edgeN=0,i=0;i<n;i++) headg[i]=-1,mark[i]=0,deg[i]=0;
	    for(i=1;i<n;i++) scanf("%d%d",&u,&v),addedge(u-1,v-1),addedge(v-1,u-1);
	    for(tail=0,i=0;i<n;i++) if(deg[i]==1) q[tail++]=i;
	    for(i=0,tot=0;i<tail;i++){
			tot+=dfs(q[i]);
		    //printf("--\n");
		}
	  //  for(i=0;i<tail;i++) printf("^%d\n",q[i]+1);
		printf("%d\n",tot);
	}
    return 0;
}

No.2

#include <stdio.h>
struct stct0{
	int v,next;
}edge[200020];
int tot,edgeN;
int headg[100010],mark[100010],deg[100010];
void dfs(int pos,int _f){
	int i,flag;
	//printf("#%d %d\n",pos+1,_f);
	mark[pos]=1;
	flag=1+_f;
	if(deg[pos]>=3){
	    for(i=headg[pos];~i;i=edge[i].next){
	        if(mark[edge[i].v]==0){
			    if(deg[edge[i].v]<3){
				    flag--;
				}
			}
	    }
	}
	if(flag<0) flag=0;
	for(i=headg[pos];~i;i=edge[i].next){
        if(mark[edge[i].v]==0){
			if(deg[pos]>=3){
			    if(deg[edge[i].v]>=3){
					if(flag) flag--,dfs(edge[i].v,0);
					else tot--,dfs(edge[i].v,1);
			    }else dfs(edge[i].v,0);
			}else dfs(edge[i].v,0);
		}
	}
	return;
}
void addedge(int u,int v){
	edge[edgeN].v=v;
	edge[edgeN].next=headg[u];
	headg[u]=edgeN++;
	deg[u]++;
    return;
}
main(){
	int i,n,u,v;
	while(~scanf("%d",&n)){
		for(i=0,edgeN=0;i<n;i++) headg[i]=-1,mark[i]=0,deg[i]=0;
	    for(i=0;i<n-1;i++) scanf("%d%d",&u,&v),addedge(u-1,v-1),addedge(v-1,u-1);
	    for(tot=-1,i=0;i<n;i++) tot+=(deg[i]==1);
	    for(i=0;deg[i]-1;i++);
		dfs(i,0);
		printf("%d\n",tot);
	}
    return 0;
}