比赛 20110923 评测结果 C
题目名称 拜访奶牛 最终得分 0
用户昵称 Makazeu 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-23 21:59:15
显示代码纯文本
#include <iostream>
using namespace std;
const int maxn=200000;
int s[maxn],
    e[maxn],
	start[maxn],
	next[maxn];
int m,n,
	i,k,
	d[maxn],
	p[maxn];
int f[maxn][2];
bool flag[maxn];

void BFS()
{
	d[1]=1;
	int l=1,
	    r=1,
		k;
	for (int i=2;i<=n;i++)
	{
		flag[i]=1;
	}		
	while (l<=r)
	{
		for (int i=start[d[l]];i!=0;i=next[i])
		{
			if (flag[e[i]])
			{
				r++;
				d[r]=e[i];
				flag[e[i]]=0;
				p[e[i]]=d[l];
			}
		}
		l++;
	}
}

void init()
{
	cin>>n;
	for (i=1;i<=n;i++)
		start[i]=0;
	for (i=1;i<n;i++)
	{
		cin>>s[i]>>e[i];
		next[i]=start[s[i]];
		start[s[i]]=i;
	}
	m=n-1;
	for (i=n;i<=2*n;i++)
	{
		s[i]=e[i-m];
		e[i]=s[i-m];
		next[i]=start[s[i]];
		start[s[i]]=i;
	}
	m+=m;
}

void solve()
{
	for (i=1;i<=n;i++)
		f[i][1]=1,f[i][0]=0;
	for (i=n;i>=1;i--)
	{
		k=d[i];
		f[p[k]][1]+=f[k][0];
		if (f[k][0]>f[k][1]) 
			f[p[k]][0]+=f[k][0];
		else f[p[k]][0]+=f[k][1];
	}
}

int main()
{
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	init();
	BFS();
	solve();
	cout<<max(f[1][0],f[1][1])<<endl;
	return 0;
}