解题思路

给定一棵树，要求删除最多的边，使得剩下的连通分量的大小都是偶数。

我们可以使DFS来解决这个问题。

AC code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> v[N]; // 存储树的邻接表
int n , a , b;
int ans[N]; // 存储每个节点为根的子树的大小
// 深度优先搜索遍历树，并计算每个节点为根的子树的大小
int dfs(int x , int fa) {
    ans[x] = 1; // 初始化当前节点为根的子树大小为1
    for(int i = 0 ; i < v[x].size() ; i++) {
        int j = v[x][i];
        if(j == fa) {
            continue;
        }
        ans[x] += dfs(j , x); // 递归计算子节点为根的子树大小，并累加到当前节点的子树大小中
    }
    return ans[x]; // 返回当前节点为根的子树大小
}
int main() {
    cin >> n;
    if(n % 2 == 1) {
        cout << -1; // 如果节点数为奇数，无法满足每个子树大小为偶数的条件，直接输出-1
        return 0;
    }
    for(int i = 1 ; i <= n - 1 ; i++) {
        cin >> a >> b;
        v[a].push_back(b); // 构建树的邻接表
        v[b].push_back(a);
    }
    dfs(1 , 0); // 从根节点开始遍历树
    int cnt = 0;
    for(int i = 1 ; i <= n ; i++) {
        if(ans[i] % 2 == 0) cnt++; // 统计子树大小为偶数的节点个数
    }
    cout << cnt - 1; // 输出可以删除的边数（子树大小为偶数的节点个数减1）
    return 0; // 养成好习惯
}