C++ 解法, 执行用时: 599ms, 内存消耗: 50312K, 提交时间: 2021-11-23 16:08:19

#include<bits/stdc++.h>
using namespace std;
int n,s,i,f[500002][3],x,y;
vector<int>a[500002];
void dp(int x,int u)
{
	f[x][1]=1;
	for(int i=0;i<a[x].size();i++)
	{
		int y=a[x][i];
		if(y==u)continue;
		dp(y,x);
		f[x][0]+=max(f[y][0],f[y][1]);
		f[x][1]+=f[y][0];
	}
}int main()
{
	cin>>n>>s;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}dp(s,-1);
	cout<<f[s][1];
}

C++14(g++5.4) 解法, 执行用时: 551ms, 内存消耗: 54980K, 提交时间: 2019-07-12 16:18:13

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5e5+5;
int n,s,f[N],g[N];vector<int>E[N];
void dfs(int u,int fa){
	f[u]=1;
	for(int v:E[u])
		if(v!=fa)
			dfs(v,u),f[u]+=g[v],g[u]+=max(f[v],g[v]);
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),E[x].push_back(y),E[y].push_back(x);
	dfs(s,0);printf("%d\n",f[s]);return 0;
}