比赛 |
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;
}