思路与算法

把无向树以1为根，迭代建立父亲和访问次序，逆序计算。令best[u]为u子树的最大匹配数，freeRoot[u]为u不与任何孩子匹配时的子树最大匹配数。

先令sum为所有孩子best之和，freeRoot[u]=sum。若u不匹配孩子，best也可取sum；若u匹配某个孩子v，其他孩子w取best[w]，该孩子必须保持根可用，所以候选为sum-best[v]+freeRoot[v]+1。枚举u的每个孩子取最大。

正确性说明

当u没有匹配某个孩子时，各孩子子树互不相交，可以独立取最优并求和。当u匹配v时，u只能使用这一条相邻匹配边，v也不能再匹配自己的孩子，因此v的状态必须是freeRoot[v]；其他子树仍独立最优。树的边只在父子之间，所有合法匹配按u是否与某个孩子相连都被上述分类恰好覆盖。叶子两状态都是0，按子树归纳得到准确状态，根的best即全树最优。

复杂度

每个节点初始化O(1)，每条边在建立次序、求孩子和及枚举匹配孩子中只处理常数次，总时间O(n)，空间O(n)。初始化parent、best、freeRoot数组O(n)已计入。最大20万节点使用迭代次序，避免深递归。

易错点

匹配限制每个节点最多属于一条选中边，不能独立选所有孩子边。匹配u-v时必须扣除v原best，再改用freeRoot[v]加一。单节点答案0，星形最多1。独立答案采用叶子配对消去法，并用50棵小树枚举全部边子集核验。

参考代码（C++11）

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1, a, b; i < n; ++i) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> parent(n + 1), order{1}, best(n + 1), freeRoot(n + 1);
    for (size_t i = 0; i < order.size(); ++i) {
        int u = order[i];
        for (int v : g[u])
            if (v != parent[u]) {
                parent[v] = u;
                order.push_back(v);
            }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i], sum = 0;
        for (int v : g[u])
            if (parent[v] == u)
                sum += best[v];
        freeRoot[u] = best[u] = sum;
        for (int v : g[u])
            if (parent[v] == u)
                best[u] = max(best[u], sum - best[v] + freeRoot[v] + 1);
    }
    cout << best[1] << '\n';
}