小红的树上删边
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红拿到了一棵树，她希望删除一些边，使得每个连通块的大小是偶数。请你帮小红计算最多删除多少条边。
请python同学加上以下扩栈代码并使用python3提交，不要用pypy3！或者使用非递归做法。
sys.setrecursionlimit(200000)输入描述：
第一行输入一个正整数n nn，代表树的节点数量。
接下来的n − 1 n−1n−1行，每行输入2 22个正整数u , v u,vu,v，代表节点u uu和节点v vv有一条边连接。
1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤105
1 ≤ u , v ≤ n 1≤u,v≤n1≤u,v≤n
输出描述：
如果无解，请输出− 1 -1−1。
否则输出一个整数，代表可以删除的最多边数。
示例1
输入：
4 1 2 2 3 3 4输出：
1说明：
删除2 − 3 2-32−3这条边即可。
示例2
输入：
3 1 2 2 3输出：
-1解题思路
首先判断树的总节点数n是否为奇数，若是则无法分割为多个偶数大小的连通块，直接输出− 1 -1−1；若n nn为偶数，先构建树的邻接表，通过D F S DFSDFS从根节点1 11遍历整棵树，计算每个节点为根的子树大小s z [ i ] sz[i]sz[i]（初始s z [ t ] = 1 sz[t]=1sz[t]=1，累加所有子节点的s z szsz值）；随后遍历除根节点外的所有节点，统计其子树大小为偶数的数量，该数量即为可删除的最多边数（删除该节点与父节点的边后，子树成为独立的偶数大小连通块，且此统计方式能保证删边数最大化）；该方法通过D F S DFSDFS高效计算子树大小，时间复杂度为O ( n ) O(n)O(n)，适配n nn达1 e 5 1e51e5的规模，先排除无解场景，再精准统计符合条件的边数，得到最多可删除的边数。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;constll M=1e6+10;ll h[N],e[M],ne[M],idx=0;ll sz[N];voidinit(ll n){for(ll i=1;i<=n;i++)h[i]=-1;}voidadd(ll a,ll b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}voiddfs1(ll t,ll r){sz[t]=1;for(ll i=h[t];i!=-1;i=ne[i]){ll x=e[i];if(x==r)continue;dfs1(x,t);sz[t]+=sz[x];}}intmain(){ll n;cin>>n;init(n);for(ll i=1;i<n;i++){ll a,b;cin>>a>>b;add(a,b);add(b,a);}if(n%2){cout<<-1<<endl;return0;}dfs1(1,0);ll ans=0;for(ll i=2;i<=n;i++){if(sz[i]%2==0)ans++;}cout<<ans<<endl;return0;}
