题意
给个一棵树，初始所有边都是白色；每次操作选择两个叶子，要求它们之间所有边为白色，将这些边染黑，直到无法操作为止。问至少需要多少次操作。(nleq 5 imes 10^5)
题解
考虑对于一个子树内贪心。一个子树内最多可能有两个叶子留到父亲，考虑一个点分别有多少儿子留下了一个/两个叶子，将留了两个的两两配对，留了一个的同理，留了两个的如果有剩则与留了一个的配对。
#include<bits/stdc++.h>
using namespace std;
int getint(){ int x;scanf("%d",&x);return x; }
const int N=5e5+10;
vector<int>to[N];
int ans=0;
int ss(int x,int fa){
if(to[x].size()==1)return 1;
int c[3]={0,0,0};
for(int v:to[x]){
if(v==fa)continue;
c[ss(v,x)]++;
}
while(c[1]>2)c[1]-=2,++ans;
while(c[2]>1)c[2]-=2,++ans;
if(c[1]>=2&&c[2]>=1)c[1]=1,c[2]-=1,++ans;
// cerr<<"> "<<x<<" "<<c[1]<<" "<<c[2]<<endl;
return min(2,c[1]+c[2]*2);
}
int main(){
// freopen("A2.in","r",stdin);
// freopen("A1.out","w",stdout);
int n=getint();
if(n==1)return puts("0"),0;
if(n==2)return puts("1"),0;
for(int i=0;i<n-1;i++){
int x=getint(),y=getint();
to[x].push_back(y);
to[y].push_back(x);
}
int rt=1;
while(to[rt].size()==1)++rt;
ans+=ss(rt,0)/2;
cout<<ans<<endl;
}
花絮：本题的搬题人的数据包中有几个数据点输出为空
