题解 | 小红的树上删边

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
vector<int>e[N];
int sz[N];

int n;
int ans = 0;
void dfs(int u,int fa)
{
    sz[u]=1;
    for(auto v:e[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        if(sz[v]%2==0)ans++;
        sz[u]+=sz[v];
    }

}

int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    if(n%2==1)
    {
        cout<<-1<<'\n';
        return 0;
    }
    dfs(1,0);
    
    cout<<ans<<'\n';


    
    return 0;
}

先特判下总结点数是奇数还是偶数，奇数的话无解，当发现子树的结点数为偶数时候，则可以删边，因为偶数-偶数还是偶数，所以剩下的联通块结点数还是偶数，dfs递归删边