记录编号	193146	评测结果	AAAAAAAAAA
题目名称	[Squarefk] 树链剖分	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.188 s
提交时间	2015-10-14 00:51:47	内存使用	1.45 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> map[100005];
inline void open()
{
	freopen("treea.in","r",stdin);
	freopen("treea.out","w",stdout);
}
int N,ans=0;
inline bool dfs(int v,int fa)
{
	int next;int son=0;int cnt=0;
	for(int i=0;i<map[v].size();i++)
	{
		next=map[v][i];
		if(next==fa) continue;
		son++;
		if(dfs(next,v))
			cnt++;
	}
	if(son-cnt>1)
	{
		ans+=(son-cnt-1);
		return 1;
	}
	return 0;
}
int main()
{
	open();
	int i,a,b;
	scanf("%d",&N);
	for(i=1;i<N;i++)
	{
		scanf("%d%d",&a,&b);
		map[a].push_back(b);
		map[b].push_back(a);
	}
	if(!dfs(1,-1))
		ans++;
	printf("%d\n",ans); 	
	return 0;
}