小红的树上删边【牛客tracker 每日一题】

小红的树上删边

时间限制：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;}