D题解 | #小红的树上删边#

根据题意显然可得，若从一个节点断掉一条边，以这个节点为根节点的子树大小是偶数的话，是不会影响剩余节点的奇偶性的，所以断边等于没断，那么断边其实是不需要我们真正进行操作的

既然切断一棵大小是偶数的子树不会影响剩下的奇偶性，那么我们就进行贪心即可，尽可能多的去切断一棵大小是偶数的子树，所以只要进行一次dfs，每次遇到一棵符合条件(即大小为偶数)的子树就切断它(不需要真的操作，只需要记录“切断”次数)就可以了

但其实这样会额外操作一次，具体可以自己举例子试试，所以我们要最后把操作次数-1(我的代码是直接把计数器初始化为-1)

时间复杂度O(n)

#include <bits/stdc++.h>
 
using LL = long long;
using PII = std::pair<LL, LL>;

const int MOD = 1e9 + 7;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> size(n + 1, 1);
    std::vector<std::vector<int>> g(n + 1, std::vector<int>()); 
    for(int i = 2; i <= n; i++) {
        int a, b;
        std::cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    if(n%2) {
        std::cout << -1 << '\n';
        return;
    }

    int res = -1;
    std::function<void(int, int)> dfs = [&](int u, int fa) {
        for(const auto& ver : g[u]) {
            if(ver == fa) continue;
            dfs(ver, u);
            size[u] += size[ver]; //计算子树大小
        }
        
        if(size[u]%2 == 0) res++; //若子树大小为偶数就切断
    };
    std::cout << res << '\n';
}
  
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
     
    int T = 1;
    //std::cin >> T;
    while (T--) solve();
    return 0;
}