黄题炸了，玄关求调

P2899

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100010],b[100010];
vector<int> G[100010];
int dp[100010][4],g[100010]; //dp[i][0]被自己覆盖，dp[i][1]被儿子覆盖，dp[i][2]被父亲覆盖 
void dfs(int now,int fa){
    int tot=0;
    dp[now][0]=1;
    for(auto v:G[now]){
        if(v==fa) continue;
        dfs(v,now);
        dp[now][0]+=min(dp[v][0],min(dp[v][2],dp[v][1]));
        dp[now][2]+=min(dp[v][0],dp[v][1]);
        dp[now][1]+=dp[v][0];
        g[++tot]=dp[v][1]-dp[v][0];
    }
    if(tot==0){
        dp[now][1]=1e9;
    }
    else{
        sort(g+1,g+tot+1);
        for(int i=1;i<tot;i++){
            if(g[i]<0){
                dp[now][1]+=g[i];
            }
            else{
                break;
            }
        }   
    }
}
signed main(){
//  freopen("P2899_6.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a[i]>>b[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    dfs(a[1],0);
    cout<<min(dp[a[1]][0],dp[a[1]][1]);
    return 0;
}