比赛 20191218 评测结果 AAAAAAAAAA
题目名称 拜访奶牛 最终得分 100
用户昵称 ShallowDream雨梨 运行时间 0.044 s
代码语言 C++ 内存使用 5.13 MiB
提交时间 2019-12-18 19:23:07
显示代码纯文本
    #include<bits/stdc++.h>
    #define ll long long 
    using namespace std;
    const int maxn=1e5+5;
    int tot,head[maxn],f[maxn][2];
	struct road{int to,next,v;}a[maxn*2];
    void add(int x,int y){
    f[x][1]=1;
	a[++tot].to=y;
	a[tot].next=head[x];head[x]=tot;}
	void dfs(int x,int fa){
	for(int i=head[x];i;i=a[i].next){
	int to=a[i].to;
	if(to==fa)continue;
	dfs(to,x);
	f[x][0]+=max(f[to][0],f[to][1]);
	f[x][1]+=f[to][0];}}
    int main(){
    freopen("vacation.in","r",stdin);
    freopen("vacation.out","w",stdout);
  	int n,q,w;
  	cin>>n;
  	for(int i=1;i<n;i++){
  	cin>>q>>w;add(q,w);add(w,q);}
  	dfs(1,0);
  	cout<<max(f[1][0],f[1][1]);
    return 0;
    }