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