该问题本质上是一个树的分解（Tree Partitioning）问题。我们需要将一棵包含 个节点的树分解成尽可能多的连通块（Connected Components），且需满足一个硬性约束条件：每个连通块的节点数必须为偶数。

关键约束：

  • 总节点数奇偶性： 如果一棵树的总节点数 是奇数，那么无论如何切割，都不可能将其划分为若干个大小均为偶数的集合（因为偶数之和必为偶数）。因此，如果 为奇数，直接判定无解（输出 -1）。
  • 连通性与无环： 输入数据保证是一棵树，这意味着任意两点间有且仅有一条路径，不存在环路。这为我们使用动态规划（DP）或深度优先搜索（DFS）提供了拓扑基础。
  • 切割与连通块数量的关系：
    • 每删除一条边，连通块的数量增加 1。
    • 要使删除的边数最多，等价于要使最终获得的连通块数量最多。
    • 在总节点数固定的情况下，连通块数量最多，意味着每个连通块的大小应尽可能小（最小的偶数正整数为 2）。

贪心策略结合DFS

针对 的数据规模，我们需要一个时间复杂度为 的算法。

策略：后序遍历（Bottom-Up）的贪心算法 我们采用贪心思想：在遍历树的过程中，一旦发现某个子树当前的节点总数为偶数，我们就立即将该子树与其父节点之间的边“剪断”。

算法正确性证明： 假设当前我们在节点 ，且以 为根的子树（含 及其所有后代）的节点总数 为偶数。

  1. 局部最优： 如果我们切断 和其父节点 的边，以 为根的部分形成了一个合法的偶数连通块。
  2. 全局影响：
    • 如果不切断， 个节点（偶数）将合并到父节点 的子树中。
    • 对于父节点 而言，加上一个偶数 并不会改变 所在连通块节点数的奇偶性（偶数 + 偶数 = 偶数；奇数 + 偶数 = 奇数）。
    • 因此，保留这条边并不会帮助父节点 将奇数大小的连通块变成偶数大小，反而仅仅是增大了一个潜在连通块的大小，从而减少了总的连通块数量（即减少了可删除边的数量）。
    • 所以，逢偶即断是全局最优策略。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    if (n % 2 == 1) {
        cout << "-1\n";
        return 0;
    }

    int ans = 0;
    auto dfs = [&](auto&& self, int u, int parent) -> int {
        int uSize = 1; // node u

        for (int v : graph[u]) {
            if (v == parent)
                continue;
            int vSize = self(self, v, u);
            if (vSize % 2 == 0) {
                ans++;
            } else {
                uSize += vSize;
            }
        }

        return uSize;
    };

    dfs(dfs, 1, -1);

    cout << ans << "\n";
}

算法复杂度分析

  • 时间复杂度：

    • 构建邻接表需要遍历所有边，耗时 。
    • DFS 遍历每个节点仅访问一次，每条边访问两次（进与出），耗时 。

  • 空间复杂度：

    • 邻接表存储图结构需要 空间。
    • DFS 递归调用栈的深度取决于树的高度。最坏情况（链状树）为 ，平均情况为 。