把树以 1 为根取出父亲先于儿子的序,倒序自底向上贪心:节点与父亲都还空着就把这条边配掉,O(n) 得到树的最大匹配数。
OJ: roj
题目 ID: 2142
难度:普及+/提高-
标签:树贪心匹配python
创建: 2026-10-08 07:55
更新: 2026-10-08 07:55
形式化题目
给定一棵有
求
正解
思路
先看通用做法的代价。 树是二分图,套匈牙利算法是
关键观察:把子树做完再回头决定父边。
任意取一个根(习惯取
- 当
的整棵子树内部已经完全决策完毕,此时如果 与 都还没有被任何匹配边占用, 那就应当把边 计入匹配。 - 理由是交换论证:假设最优解
里不含 ,而 、 此刻都空着。 若 在 中与某个子树内的点配对,那和"子树已决策完毕且 仍空着"矛盾; 所以 在 里最多与某个子树外的点在另一条边 上配对。 把 换成 : 的占用情况不变, 从"被占用"变成"空闲", 从"空闲"变成"被占用", 不变,仍然合法。也即"配 "不会比不配更差。 如果 在 里就是空闲的,那么直接加上 还会把答案 +1。
这条规则对每一个节点都成立,而且它的执行顺序天然自洽:只要保证处理
注意"先把子节点全部递归完,回溯时再占用
验证直觉的两个极端结构:
- 长链
:每层都能配上,答案是 ; - 菊花图(
连所有其余点): 只能供一条边用,答案是 。
为什么不用树形 DP? 树形 DP(
代码
Python 版(同目录 main.py):
#!/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++ 版(同一算法):
/**
* 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:setrecursionlimit 也有风险。
这里改用 order 数组充当 BFS 队列(Python 直接 for u in order: 边遍历边追加),
得到"父亲先于儿子"的序后倒扫,等价于后序遍历而不占栈空间。
复杂度
- 时间:
。BFS 一遍把 条有向边各访问一次,倒序扫描一遍 个节点、 每个节点做一次 判定。 时总运算量在 量级。 - 空间:
。邻接表存 个整数,另有 parent、order、matched三个长度的数组,C++ 侧约 字节, 远低于 512 MB 限制。 - 与 C++ 解法的关系:两边是同一个算法,复杂度同为
;Python 侧主要成本在 读入与邻接表的构建( 次 append),量级仍是 次操作, 在原时限内可过;C++ 用 vector邻接表 + 快速读入,余量非常充足。
总结
- 树上匹配不用学网络流:树是天然的层次结构,“子树内部先决策完、再决定与父亲的那条边”
就足以覆盖所有最优解,问题从
降到 。 - 交换论证是贪心的依据:把"空闲的
配上父边"与"最优解中 的配对"对调, 答案不减少,这就是本文贪心成立的唯一支柱;写贪心时先想清楚这一步,比背结论可靠。 - 顺序即正确性:本文算法只有两条语句,但顺序错了就全错—— 必须"儿子先于父亲"地判定,倒序扫描 BFS 序就是最省事的实现方式。
- 别用递归碰长链:
的链足以让递归 DFS 爆栈, 用显式数组(BFS 序 + 倒扫)代替后序遍历是本题最值得记住的实现细节。
数据来源说明:素材源目录中存在数据生成脚本(
data.py), 说明配套data/是自造的 10 个单测点(、 、题面样例、随机树、 完全二叉树、链、星形、扫帚),题面也属网络重建, 与官方原题的分值与数据分布可能存在偏差;本文的算法与复杂度分析不依赖该数据分布, 已对全部 10 个真实测点逐一实测通过。