其实整个问题是具有可DP性的，以1为根，设dp[i][0/1]表示：

• dp[i][0] 表示 以i节点为根的子树，不需要父节点的安利的情况下，自己内部能全部用上CourseBench的代价。
• dp[i][1] 表示 以i节点为根的子树，需要父节点的安利的情况下，自己内部能全部用上CourseBench的代价。

注意到dp[i][0] >= dp[i][1]

然后dp就行了。

设当前点度数为deg,$k=\lfloor {\deg\over 2} \rfloor$转移为：

• 把自己染黑，$=\sum \min (dp[u][0],dp[u][1])+1$
• dp[i][0]: 选择子树最小的$k$个dp[u][0]，剩下加上dp[u][1]
• dp[i][1]: 选择子树最小的$k-1$个dp[u][1]，剩下加上dp[u][1]

#include<bits/stdc++.h>
using namespace std;
int qr(){
	int ret=0,c=getchar();
	while(!isdigit(c)) c=getchar();
	while( isdigit(c)) ret=ret*10+c-48,c=getchar();
	return ret;
}
const int maxn=1e6+5;
int n;
vector<int>e[maxn];
int dp[maxn][2];

void add(int fr,int to){
	e[fr].push_back(to);
	e[to].push_back(fr);
}

void dfs(int now,int last){
	for(auto t:e[now])
		if(t^last)
			dfs(t,now);
	int k=(e[now].size()+1)/2,sum=0;
	vector<int>ve,fe;
	for(auto t:e[now])
		if(t^last)
			ve.push_back(min(dp[t][0],dp[t][1])),fe.push_back(dp[t][0]-ve.back()),sum+=ve.back();
	sort(ve.begin(),ve.end());
	sort(fe.begin(),fe.end());
	//dp(i,0)
	dp[now][0]=dp[now][1]=sum+1;
	if((int)ve.size()>=k){
		int sum2=0;
		for(int t=0;t<k;++t)
			sum2+=fe[t];
		dp[now][0]=min(dp[now][0],sum2+sum);
	}
	if((int)ve.size()>=k-1){
		int sum2=0;
		for(int t=0;t<k-1;++t)
			sum2+=fe[t];
		dp[now][1]=min(dp[now][1],sum2+sum);
	}
	//cout<<dp[now][0]<<' '<<dp[now][1]<<endl;
}

int main(){
	n=qr();
	for(int t=1;t<n;++t)
		add(qr(),qr());
	dfs(1,0);
	cout<<dp[1][0]<<endl;
	return 0;
}