比赛 |
20191218 |
评测结果 |
AAAAAAAAAA |
题目名称 |
拜访奶牛 |
最终得分 |
100 |
用户昵称 |
数声风笛ovo |
运行时间 |
0.010 s |
代码语言 |
C++ |
内存使用 |
3.42 MiB |
提交时间 |
2019-12-18 21:05:45 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int cnt=0,head[maxn],f[maxn][2];
struct edgeqwq{
int to,next,dis;
}edge[2*maxn];
void add(int from,int to){
f[from][1]=1;
edge[++cnt].to=to;
edge[cnt].next=head[from];
head[from]=cnt;
return ;
}
void dfs(int u,int fa){
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(v==fa){
continue;
}
dfs(v,u);
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
return ;
}
int main(){
freopen("vacation.in","r",stdin);
freopen("vacation.out","w",stdout);
int n,a,b;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1,0);
cout<<max(f[1][0],f[1][1]);
return 0;
}