树边匹配

GitHub跳转原题关系图返回列表

把树以 1 为根取出父亲先于儿子的序,倒序自底向上贪心:节点与父亲都还空着就把这条边配掉,O(n) 得到树的最大匹配数。

OJ: roj

题目 ID: 2142

难度:普及+/提高-

标签:树贪心匹配python

创建: 2026-10-08 07:55

更新: 2026-10-08 07:55

形式化题目

给定一棵有 nn 个节点的树 T=(V,E)T = (V, E),∣V∣=n|V| = n、∣E∣=n−1|E| = n - 1,节点编号为 1,2,…,n1, 2, \dots, n。 要求选出一个边集 M⊆EM \subseteq E,使得每个节点至多是 MM 中一条边的端点,即

∀ u∈V:∣{e∈M:u∈e}∣⩽1. \forall\, u \in V: \quad |\{e \in M : u \in e\}| \leqslant 1 .

求 ∣M∣|M| 的最大值,这就是树的最大匹配数。约束 1⩽n⩽2⋅1051 \leqslant n \leqslant 2 \cdot 10^5, 1⩽a,b⩽n1 \leqslant a, b \leqslant n。

正解

思路

先看通用做法的代价。 树是二分图,套匈牙利算法是 O(n2)O(n^2)、套 Dinic/Hopcroft-Karp 是 O(nn)O(n \sqrt{n}):n=2⋅105n = 2 \cdot 10^5 时前者必然超时,后者运算量约 9⋅1079 \cdot 10^7 且常数不小, 在 1000 ms 里很危险。而枚举每条边"选或不选"是 O(2n−1)O(2^{n-1}),n=30n = 30 就撑不住。 所以必须用上"树无环、层次清晰"这个结构。

关键观察:把子树做完再回头决定父边。

任意取一个根(习惯取 11),得到"父亲先于儿子"的层级结构。考察任意节点 uu 与它的父亲 pp:

  • 当 uu 的整棵子树内部已经完全决策完毕,此时如果 uu 与 pp 都还没有被任何匹配边占用, 那就应当把边 (u,p)(u, p) 计入匹配。
  • 理由是交换论证:假设最优解 M∗M^* 里不含 (u,p)(u, p),而 uu、pp 此刻都空着。 若 uu 在 M∗M^* 中与某个子树内的点配对,那和"子树已决策完毕且 uu 仍空着"矛盾; 所以 uu 在 M∗M^* 里最多与某个子树外的点在另一条边 e=(u,w)e = (u, w) 上配对。 把 ee 换成 (u,p)(u, p):uu 的占用情况不变,ww 从"被占用"变成"空闲", pp 从"空闲"变成"被占用",∣M∗∣|M^*| 不变,仍然合法。也即"配 (u,p)(u, p)"不会比不配更差。 如果 uu 在 M∗M^* 里就是空闲的,那么直接加上 (u,p)(u, p) 还会把答案 +1。

这条规则对每一个节点都成立,而且它的执行顺序天然自洽:只要保证处理 uu 的时候 uu 的所有儿子都已经处理过,uu 的空闲状态就是最终状态。于是取 BFS 得到的序 orderorder(父亲必在儿子之前),倒序扫描 orderorder,每个节点被扫到时儿子都已经决策完, 只需一次判定:

若 parent(u)≠0  ∧  ¬matched(u)  ∧  ¬matched(parent(u))⟹matched(u)=matched(parent(u))=true,  ans←ans+1. \text{若 } \mathrm{parent}(u) \neq 0 \;\wedge\; \neg \mathrm{matched}(u) \;\wedge\; \neg \mathrm{matched}(\mathrm{parent}(u)) \quad\Longrightarrow\quad \mathrm{matched}(u) = \mathrm{matched}(\mathrm{parent}(u)) = \texttt{true},\; ans \leftarrow ans + 1 .

注意"先把子节点全部递归完,回溯时再占用 uu"的顺序是硬性的: 若在进入子节点之前就占用 uu,子树内部本来能配上的边会被白白破坏。 倒序扫描自带这个顺序,不需要递归。

验证直觉的两个极端结构:

  • 长链 1−2−⋯−n1 - 2 - \dots - n:每层都能配上,答案是 ⌊n/2⌋\lfloor n/2 \rfloor;
  • 菊花图(11 连所有其余点):11 只能供一条边用,答案是 11。

为什么不用树形 DP? 树形 DP(dp[u][0/1]dp[u][0/1] 表示 uu 是否与某个儿子配对, dp0[u]=∑vbest[v]dp0[u] = \sum_v best[v],best[u]=max⁡(dp0[u],dp0[u]+max⁡v(dp0[v]−best[v])+1)best[u] = \max(dp0[u], dp0[u] + \max_v(dp0[v] - best[v]) + 1)) 当然也能 O(n)O(n) 解决,但需要两个数组、一次自底向上合并,常数与出错面积都比贪心大。 贪心只需要一个布尔数组和一次判定,是本题最短的正确写法。

代码

Python 版(同目录 main.py):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 11:30
# update_at: 2026-10-12 14:52

# 树的最大匹配:自底向上贪心——儿子都决策完后,u 与父亲都还空着就配掉父边。
# 一个结点的字段聚合成 Node 对象:父亲编号 + 是否已被匹配边占用,
# 对应 fa[] / matched[] 两个平行列表,这里收进同一个对象。
# 如何使用:
# 1. init(n)          造出 0..n 共 n+1 个结点和空邻接表
# 2. add_edge(a, b)   n-1 条边两个方向都存,BFS 时才走得通
# 3. bfs_order()      以 1 为根求"父亲先于儿子"的序(显式队列,不递归)
# 4. greedy_match()   倒着扫序做贪心配对,返回匹配边数
# 注意:n = 2e5 的链形数据会让递归 DFS 爆栈,所以全程用显式队列。

import sys


class Node:
    """编号 u 的结点:父亲 + 是否已被匹配边占用。"""

    def __init__(self) -> None:
        self.fa = 0          # 父亲编号,根的父亲是 0
        self.matched = False # 是否已经被某条匹配边占用


node: list[Node] = []     # node[u]:编号 u 的结点
adj: list[list[int]] = [] # adj[u]:u 的邻接表(无向树)


def init(n: int) -> None:
    """造出 0..n 共 n+1 个结点和空邻接表。"""
    global node, adj
    node = [Node() for _ in range(n + 1)]
    adj = [[] for _ in range(n + 1)]


def add_edge(u: int, v: int) -> None:
    """加一条无向边:树边两个方向都要存。"""
    adj[u].append(v)
    adj[v].append(u)


def bfs_order() -> list[int]:
    """以 1 为根做迭代 BFS,返回"父亲先于儿子"的访问序 order。

    边遍历边追加:list 迭代会看到新元素,order 自己就是队列。
    显式队列而非递归,避免 n = 2e5 的链形数据爆栈。
    """
    order = [1]
    node[1].fa = 0
    for u in order:
        for v in adj[u]:
            if v != node[u].fa:  # 树上唯一的已访邻点就是父亲
                node[v].fa = u
                order.append(v)
    return order


def greedy_match(order: list[int]) -> int:
    """自底向上贪心:倒着扫 order,u 与父亲都还空着就配 (u, fa[u])。

    u 被处理时它的所有儿子都已决策完;交换论证保证这样不会比最优解差。
    """
    ans = 0
    for u in reversed(order):
        p = node[u].fa
        if p and not node[u].matched and not node[p].matched:
            node[u].matched = node[p].matched = True
            ans += 1
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:  # 空输入
        return

    init(n)
    for _ in range(n - 1):
        a, b = next(data), next(data)
        add_edge(a, b)

    print(greedy_match(bfs_order()))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 11:30
 * update_at: 2026-10-12 14:55
 */
// main.cpp:自底向上贪心求树的最大匹配——儿子都决策完后,u 与父亲都还空着就配掉父边。
//
// 一个结点的两个字段聚合成 struct Node:父亲编号、是否已被匹配边占用,
// 对应 fa[] / matched[] 两个平行数组,这里按结点下标收进 node[u]。
// order[] 兼作显式 BFS 队列,倒着扫一遍就得到"儿子先于父亲"的后序效果,
// 全程不递归:n = 2e5 的链形数据也不会爆栈。

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

const int maxn = 200005; // 题面 n ≤ 2e5

struct Node {
    int fa;       // 父亲编号,根的父亲是 0
    bool matched; // 是否已经被某条匹配边占用
};

Node node[maxn];     // node[u]:编号 u 的结点
vector<int> g[maxn]; // g[u]:u 的邻接表(无向树)
int order[maxn];     // BFS 序兼队列:order[i] 是第 i 个出队的结点,父亲一定排在儿子前面
int n;               // 结点数
ll ans;              // 匹配边数

// 加一条无向边:树边两个方向都要存,BFS 时才走得通
void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 读入建树:n-1 条边
void read_tree() {
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
    }
}

// BFS 求"父亲先于儿子"的序:order 兼作队列,head 是队首
void bfs_order() {
    int head = 0, tail = 0;
    order[tail++] = 1;
    node[1].fa = 0; // 以 1 为根
    while (head < tail) {
        int u = order[head++];
        for (int v : g[u]) {
            if (v == node[u].fa) {
                continue; // 树上唯一的已访邻点就是父亲
            }
            node[v].fa = u;
            order[tail++] = v;
        }
    }
}

// 自底向上贪心:倒着扫 BFS 序,u 被处理时它的所有儿子都已决策完。
// u 与父亲都还空着就配 (u, fa[u]):交换论证保证这样不会比最优解差
void greedy_match() {
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        int p = node[u].fa;
        if (p != 0 && !node[u].matched && !node[p].matched) {
            node[u].matched = true;
            node[p].matched = true;
            ans++;
        }
    }
}

void solve() {
    read_tree();
    bfs_order();
    greedy_match();
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (!(cin >> n)) {
        return 0; // 空输入直接退出
    }
    solve();
    return 0;
}

两份实现都刻意避免了递归 DFS:nn 退化成链时递归深度达 2⋅1052 \cdot 10^5, C++ 会爆栈、Python 即使调大 setrecursionlimit 也有风险。 这里改用 order 数组充当 BFS 队列(Python 直接 for u in order: 边遍历边追加), 得到"父亲先于儿子"的序后倒扫,等价于后序遍历而不占栈空间。

复杂度

  • 时间:O(n)O(n)。BFS 一遍把 2(n−1)2(n-1) 条有向边各访问一次,倒序扫描一遍 nn 个节点、 每个节点做一次 O(1)O(1) 判定。n=2⋅105n = 2 \cdot 10^5 时总运算量在 10610^6 量级。
  • 空间:O(n)O(n)。邻接表存 2(n−1)2(n-1) 个整数,另有 parent、order、matched 三个长度 n+1n+1 的数组,C++ 侧约 2×2⋅105×4B+n2 \times 2 \cdot 10^5 \times 4\text{B} + n 字节, 远低于 512 MB 限制。
  • 与 C++ 解法的关系:两边是同一个算法,复杂度同为 O(n)O(n);Python 侧主要成本在 读入与邻接表的构建(2⋅1052 \cdot 10^5 次 append),量级仍是 105∼10610^5 \sim 10^6 次操作, 在原时限内可过;C++ 用 vector 邻接表 + 快速读入,余量非常充足。

总结

  • 树上匹配不用学网络流:树是天然的层次结构,“子树内部先决策完、再决定与父亲的那条边” 就足以覆盖所有最优解,问题从 O(nn)O(n\sqrt n) 降到 O(n)O(n)。
  • 交换论证是贪心的依据:把"空闲的 uu 配上父边"与"最优解中 uu 的配对"对调, 答案不减少,这就是本文贪心成立的唯一支柱;写贪心时先想清楚这一步,比背结论可靠。
  • 顺序即正确性:本文算法只有两条语句,但顺序错了就全错—— 必须"儿子先于父亲"地判定,倒序扫描 BFS 序就是最省事的实现方式。
  • 别用递归碰长链:n=2⋅105n = 2 \cdot 10^5 的链足以让递归 DFS 爆栈, 用显式数组(BFS 序 + 倒扫)代替后序遍历是本题最值得记住的实现细节。

数据来源说明:素材源目录中存在数据生成脚本(data.py), 说明配套 data/ 是自造的 10 个单测点(n=1n=1、n=2n=2、题面样例、随机树、 完全二叉树、链、星形、扫帚),题面也属网络重建, 与官方原题的分值与数据分布可能存在偏差;本文的算法与复杂度分析不依赖该数据分布, 已对全部 10 个真实测点逐一实测通过。