参考第二篇题解的写法

对于dfs部分，注释内的dfs个人认为可以优化减少码量

但用注释内的dfs函数WA #2 #5

#include<bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
int const X=1e6+100;
int n,u,v,f[X][3];
vector<int> e[X];
/*
void dfs(int rt,int fa){
	f[rt][0]=1;
	int add=f[e[rt][0]][0]-min(f[e[rt][0]][0],f[e[rt][0]][1]);
	for(int i=0;i<e[rt].size();i++){
		int to=e[rt][i];
		if(to==fa) continue;
		dfs(to,rt);
		f[rt][0]+=min(f[to][0],min(f[to][1],f[to][2]));
		f[rt][2]+=min(f[to][0],f[to][1]);
		f[rt][1]+=min(f[to][0],f[to][1]);
		if(add > (f[to][0]-min(f[to][1],f[to][0]))){
			//找出贡献最小的x 
			add=f[to][0]-min(f[to][1],f[to][0]);
		}
	}
	f[rt][1]+=add;
	return ; 
}
*/
void dfs(int rt,int fa){
	f[rt][0]=1;
	int x=0;
	for(int i=0;i<e[rt].size();i++){
		int to=e[rt][i];
		if(to==fa) continue;
		dfs(to,rt);
		f[rt][0]+=min(f[to][0],min(f[to][1],f[to][2]));
		f[rt][2]+=min(f[to][0],f[to][1]);
		
		if((f[x][0]-min(f[x][0],f[x][1])) > (f[to][0]-min(f[to][1],f[to][0]))){
			//找出贡献最小的x 
			x=to;
		}
	}
	f[rt][1]=f[x][0];
	for(int i=0;i<e[rt].size();i++){
		int to=e[rt][i];
		if(to==fa || to==x) continue;
		f[rt][1]+=min(f[to][0],f[to][1]);
	}
	return ; 
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n; 
	for(int i=1;i<n;i++){
		cin>>u>>v;
		e[u].pb(v); e[v].pb(u);
	}
	f[0][0]=1e9;
	dfs(1,-1);
	cout<<min(f[1][0],f[1][1]);
	return 0;
}