记录编号	80329	评测结果	AAAWWWWWWW
题目名称	[USACO Nov10] 拜访奶牛	最终得分	30
用户昵称	Launcher	是否通过	未通过
代码语言	C++	运行时间	0.137 s
提交时间	2013-11-07 07:56:38	内存使用	14.07 MiB

#include<iostream>
#include<cstdio>
#include<memory>
using namespace std;
int n,m,l;
short a[50002][102]={0};
int f[50002]={0},c[50002]={0};
bool g[50002]={false};
int w[50002][2]={0};
int u[50002]={0};
int v[50002]={0};
int Max(int x,int y)
{
	if (x>y)
		return x;
	else
		return y;
}
void findchild(int x)
{
	int i;
	u[x]=u[f[x]]+1;
	l=Max(u[x],l);
	g[x]=false;
	for (i=1;i<=a[x][0];i++)
	if (g[a[x][i]])
	{
		c[x]++;
		f[a[x][i]]=x;
		findchild(a[x][i]);
	}
}
void dp(int x)
{
	int i,j,k,r;
	r=0;
	for (i=1;i<=n;i++)
		if (u[i]==x)
		{
			k=f[i];
			w[k][1]+=w[i][0];
			w[k][0]+=w[i][1];
		}
}
int main()
{
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	int i,j,k;
	cin>>n;
	for (i=1;i<n;i++)
	{
		g[i]=true;
		cin>>k>>l;
		a[k][0]++;
		j=a[k][0];
		a[k][j]=l;
		a[l][0]++;
		j=a[l][0];
		a[l][j]=k;
	}
	g[n]=true;
	l=0;
	for (i=1;i<=n;i++)
		if (l<a[i][0])
		{
			l=a[i][0];
			k=i;
		}
		
	f[k]=0;
	u[k]=1;
	l=0;
	findchild(k);
	//memset(a,0,sizeof(a));
	for (i=1;i<=n;i++)
	{
		w[i][1]=1;
		g[i]=false;
		if (c[i]==0)
		{
			w[i][1]=1;
			g[i]=true;
		}
	}
	for (i=l;i>=1;i--)
		dp(i);
	cout<<Max(w[k][1],w[k][0])<<endl;
	return 0;
}