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