比赛 20191218 评测结果 AAAAAAAAAA
题目名称 拜访奶牛 最终得分 100
用户昵称 fmq03 运行时间 0.125 s
代码语言 C++ 内存使用 4.65 MiB
提交时间 2019-12-18 21:06:21
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
vector<int>son[50001];
bool ismark[50001];
int ans[50001][2];
int nnum;
void dfs(int u){
	ismark[u]=true;
	for(int i=0;i<son[u].size();++i){
		int ss=son[u][i];
		if(ismark[ss]!=true){
			dfs(ss);
			ans[u][1]+=ans[ss][0];
			ans[u][0]+=max(ans[ss][1],ans[ss][0]);
		}
	}
	return;
}
int main(){
	freopen("vacation.in","r",stdin);
	freopen("vacation.out","w",stdout);
	cin>>nnum;
	for(int i=1;i<nnum;++i){
		int a,b;
		cin>>a>>b;
		son[a].push_back(b);
		son[b].push_back(a);
		ans[a][1]=1;
		ans[b][1]=1;
	}
	dfs(1);
	cout<<max(ans[1][1],ans[1][0])<<endl;
	return 0;
}