BZOJ 2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛 树形DP

#include <bits/stdc++.h> 
#define setIO(s) freopen(s".in","r",stdin)  
#define maxn 200000  
using namespace std; 
int edges;               
int f[maxn],g[maxn];   
int hd[maxn],to[maxn],nex[maxn]; 
void addedge(int u,int v)
{
	nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; 
}
void dfs(int u,int fa)
{ 
	f[u]=1,g[u]=0; 
	for(int i=hd[u];i;i=nex[i])                   
	{ 
		int v=to[i]; 
		if(v==fa) continue;  
		dfs(v,u);     
		f[u]+=g[v]; 
		g[u]+=max(g[v], f[v]);  
	}     
}
int main()
{ 
	// setIO("input");  
	int n; 
	scanf("%d",&n);    
	for(int i=1;i<n;++i) 
	{
		int x,y; 
		scanf("%d%d",&x,&y);  
		addedge(x,y), addedge(y,x);  
	}
	dfs(1,0); 
	printf("%d\n",max(f[1],g[1]));  
	return 0; 
}