题解 | 小红的树上删边

#include <vector>
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x7fffffff
#define _ << ' ' <<
using pii = std::pair<int,int>;
using ll = long long;
using std::cin;
using std::cout;
using std::vector;
using std::map;
using std::queue;
using std::priority_queue;
using std::unordered_map;
using std::string;
constexpr int maxn = 1e5+10;
template<typename T>
inline void debug(T& a){cout << a <<' ';}
inline void debug(char a) {cout << a << ' ';}
inline void debug(std::vector<int>& v) {for(int& i:v) {cout << i <<' ';} cout << endl;}
vector<int> nums;
vector<vector<int> > v;

void dfs(int k) {
    for(int i:v[k]) {
        if(v[i].empty()) {
            nums[k] += nums[i];
        } else {
            dfs(i);
            nums[k] += nums[i];
        }
    }
    return;
}

void solve() {
    int n;cin >> n;
    if(n%2) return void(cout << -1 << endl);
    v.resize(n+1);
    nums.resize(n+1,1);
    int u,d;
    vector<pii> vi(n-1);
    for(int i = 1;i<=n-1;i++) {
        cin >> u >> d;
        v[u].emplace_back(d);
    }

    dfs(1);
    int ans = 0;
    for(int i = 1;i<=n;i++) {
        if(nums[i] % 2 == 0) ans++;
    }
    cout << ans-1 << endl;
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    while(t--) {
        solve();
    }
    
    return 0;
}

今天的题目很简单，本质上是统计偶数个数的联通块的个数