比赛 20110923 评测结果 AAAWWWWWWW
题目名称 拜访奶牛 最终得分 30
用户昵称 donny 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-09-23 20:43:10
显示代码纯文本
#include <iostream>
#include <fstream>

using namespace std;

int i,j,k,l;
int f[50010][2],next[101000],a[101000];
int n,p,q;
int head,tail;

void insert(int x,int y)
{
	if (next[x]==0)
	{
		if (a[x]==0)
			a[x]=y;
		else
		{
			tail++;
			a[tail]=y;
			next[x]=tail;
		}
	}
	else
	{
		tail++;
		a[tail]=y;
		next[tail]=next[x];
		next[x]=tail;
	}
	
	if (next[y]==0)
	{
		if (a[y]==0)
			a[y]=x;
		else
		{
			tail++;
			a[tail]=x;
			next[y]=tail;
		}
	}
	else
	{
		tail++;
		a[tail]=x;
		next[tail]=next[y];
		next[y]=tail;
	}
}

void dfs(int x,int y)
{
	int i,j,k,l;
	i=a[x];
	j=next[x];
	k=1;
	l=0;
	
	while (i!=0)
	{
		if ((f[i][0]==-1)and(i!=y))
			dfs(i,x);
		if (i!=y)
		{
			k+=f[i][0];
			l+=f[i][1];
		}
		i=a[j];
		j=next[j];
	}
	f[x][0]=l;
	f[x][1]=k;
}

int main()
{
	ifstream fin("vacation.in");
	ofstream fout("vacation.out");
	
	fin>>n;
	
	tail=n;
	for (i=1;i<n;i++)
	{
		fin>>j>>k;
		insert(j,k);
	}
	
	for (i=1;i<=n;i++)
	{
		f[i][0]=-1;
		f[i][1]=-1;
	}
	
	dfs(1,0);
	
	if (f[1][1]>f[1][0])
		f[1][0]=f[1][1];
	
	fout<<f[1][0]<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}