代码：

#include <cstdio>
#include <vector>
using std::vector;
#define N 100010
//f[i]=i被自己覆盖
//g[i]=i被儿子覆盖
//h[i]=i被父亲覆盖
vector<int> e[N];
int f[N],g[N],h[N];
int n;
inline int min(int a,int b){return a<b?a:b;}
void dfs(int o,int fa=-1)
{
	f[o]=1;
	int ans=0;
	for(auto i:e[o])
		if(i!=fa)
		{
			ans++;
			dfs(i,o);
			f[o]+=h[i];
			g[o]+=f[i];
			h[o]+=g[i];
		}
	if(!ans) g[o]=0x3f3f3f3f;
	if(fa==-1) h[o]=0x3f3f3f3f;
	g[o]=min(g[o],f[o]);
	h[o]=min(g[o],h[o]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1);
	printf("%d",g[1]);//min(f[1],g[1]));
	return 0;
}

评测记录