题目链接 题意:去除尽可能多的边,使得剩下的连通块里点的个数都为偶数 解析: n为奇数结果为-1 偶数的话从一个点开始递归找节点的子节点的数目(包含本身),如果是偶数则可以直接去除,因为只有n-1个边,也就是说剩下的一定是一个偶数的连通块
#include <bits/stdc++.h> #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define pll pair<ll,ll> #define rep(i,a,b) for(int i=a;i<=b;i++) #define rep1(i,a,b) for(int i=a;i>=b;i--) #define rson rt<<1|1,m+1,r #define lson rt<<1,l,m using namespace std; const int N=2e5+100; vector<int> g[N]; int son[N]; int n,ans; void dfs(int x,int pre) { son[x]=1; for(auto i:g[x]) if (i!=pre) { dfs(i,x); son[x]=son[x]+son[i]; if (son[i]%2==0) ans++; } } int main() { #ifdef LOCAL_DEFINE freopen("D:\\rush.txt","r",stdin); #endif ios::sync_with_stdio(false),cin.tie(0); cin>>n; ans=0; for (int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; g[x].pb(y); g[y].pb(x); } dfs(1,0); if (son[1]%2!=0){ puts("-1"); return 0; } cout<<ans<<endl; }