把「恰好含一条树边的割」化归成 T-e 两侧的割,用树上边差分统计每条树边被多少条非树边跨过,答案即最小覆盖数加一。
OJ: roj
题目 ID: 1761
难度:提高+/省选-
标签:最小割生成树树上差分LCApython
创建: 2026-10-07 22:38
更新: 2026-10-07 22:38
形式化题目
给定无向无权简单图
即在"恰好包含
正解
思路
第一步:割的形状被"恰好一条树边"锁死了。
结论:一个合法的割与一条树边
(
第二步:
也就是"覆盖
第三步:一次树上差分求出所有
然后把
用样例验一遍(
| 树边 |
跨过的非树边 | 割的大小 | ||
|---|---|---|---|---|
| 2 | 3 | |||
| 2 | 3 | |||
| 1 | 2 |
最小是
LCA 怎么求。 problem10 约 main.py 换成欧拉序 + 稀疏表的
实现要点。
- 建树用迭代 BFS / 迭代 DFS,链状树(
深链是数据里的最坏形状)不会爆栈。 - 多组数据、每组上界
、 ,输入量到 个数, C++ 用 fread快读。 - 数组每次进新一组都要重置(
head置-1、diffCnt清)。 - 退化输入
: 没有边,不存在"恰好含一条 边"的割,两种实现都输出 并在代码里注明。题面约束 且无自环,所以这个分支在真实数据里不可达。
代码
Python 版(欧拉序 + 稀疏表 LCA,树上差分):
#!/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 22:38
# update_at: 2026-10-07 22:38
import sys
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Adj = list[list[int]] # 生成树的邻接表:adj[x] 是 x 的所有邻居
type Sparse = list[list[int]] # 欧拉序上的 RMQ 稀疏表,第 k 层窗口长 2^k,存深度最小的节点
type Lca = tuple[list[int], Sparse, list[int], list[int]] # (欧拉序, 稀疏表, 首次出现位置, 深度)
def rooted_tree(adj: Adj, n: int) -> tuple[list[int], list[int], list[int]]:
"""以 1 为根 BFS,返回 (父亲, 深度, BFS 序);BFS 序倒着扫就是自底向上的累加顺序。"""
par = [0] * (n + 1)
dep = [0] * (n + 1)
order = [1]
for u in order: # 边遍历边追加,等价于一个队列
for v in adj[u]:
if v != par[u]: # 树里除父亲外都是孩子,不需要额外判重
par[v] = u
dep[v] = dep[u] + 1
order.append(v)
return par, dep, order
def euler_tour(adj: Adj, par: list[int], n: int) -> tuple[list[int], list[int]]:
"""迭代 DFS 求欧拉序(长 2n-1)与每个节点首次出现的位置。
进入节点与回退到父节点各记一笔,于是 u、v 的 LCA 恰好是欧拉序上
first[u]..first[v] 这段区间里深度最小的那个节点。
"""
euler = [1]
first = [0] * (n + 1)
ptr = [0] * (n + 1) # ptr[x] 指向 adj[x] 里下一个待访问的邻居
stack = [1]
while stack:
u = stack[-1]
if ptr[u] < len(adj[u]):
v = adj[u][ptr[u]]
ptr[u] += 1
if v != par[u]:
first[v] = len(euler) # 树的 DFS 里 v 只可能由父亲首次走到
euler.append(v)
stack.append(v)
else:
stack.pop()
if stack:
euler.append(stack[-1]) # 回退到父节点,再记一笔
return euler, first
def rmq_table(euler: list[int], dep: list[int]) -> Sparse:
"""对欧拉序建稀疏表:第 k 层存窗口长 2^k 内深度最小的节点,供 O(1) 区间取最小。"""
table: Sparse = [euler] # 第 0 层窗口长 1,就是欧拉序本身
while 1 << len(table) <= len(euler):
prev = table[-1]
half = 1 << (len(table) - 1)
table.append([a if dep[a] < dep[b] else b for a, b in zip(prev, prev[half:])])
return table
def cover_counts(eu: list[int], ev: list[int], lca: Lca) -> list[int]:
"""树上边差分:每条非树边 (u,v) 给 u-v 树上路径上的每条树边加一。
树边 (par[x], x) 的值记在节点 x 上,于是每条非树边做
diff[u]++, diff[v]++, diff[LCA] -= 2;之后按 BFS 序倒着做子树和,
节点 x 的值就是覆盖树边 (par[x], x) 的非树边条数。
"""
euler, table, first, dep = lca
diff = [0] * len(dep)
for u, v in zip(eu, ev):
l, r = first[u], first[v]
if l > r:
l, r = r, l
k = (r - l + 1).bit_length() - 1 # 覆盖 [l, r] 的层号:2^k <= r-l+1
row = table[k]
a = row[l]
b = row[r - (1 << k) + 1]
w = a if dep[a] < dep[b] else b # 区间内深度最小的节点就是 LCA
diff[u] += 1
diff[v] += 1
diff[w] -= 2
return diff
def min_cut_answer(diff: list[int], order: list[int], par: list[int]) -> int:
"""恰好含一条树边的割的最小边数:树边 (par[x], x) 的覆盖数 + 1,取最小。
逆 BFS 序做子树和(孩子的值先并给父亲)之后,diff[x] 就是跨过树边
(par[x], x) 的非树边条数,于是该割的边数 = 覆盖数 + 1。
"""
for x in reversed(order[1:]):
diff[par[x]] += diff[x]
best = min((diff[x] for x in order[1:]), default=-1) # 无树边时(约束外)输出 0
return best + 1
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
n, m = next(data), next(data)
adj: Adj = [[] for _ in range(n + 1)]
for _ in range(n - 1): # 先读生成树 T 的 N-1 条边
u, v = next(data), next(data)
adj[u].append(v)
adj[v].append(u)
extra = m - n + 1 # 题面:其余 M-N+1 条边不在 T 中
eu = [0] * extra
ev = [0] * extra
for i in range(extra):
eu[i], ev[i] = next(data), next(data)
par, dep, order = rooted_tree(adj, n)
euler, first = euler_tour(adj, par, n)
diff = cover_counts(eu, ev, (euler, rmq_table(euler, dep), first, dep))
out.append(str(min_cut_answer(diff, order, par)))
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()C++ 版(同一算法,LCA 用倍增):
/**
* 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 22:38
* update_at: 2026-10-07 22:38
*/
// main.cpp:最小割(一本通 1761 / ROJ 1761)。
// 关键结论:割里恰好含 T 的一条边 e ⇔ 割的两侧就是 T-e 的两个连通块
// (T 是生成树,任一非平凡割至少跨过一条树边,跨过恰好一条就只能是 e),
// 于是该割大小 = 1 + cover[e],cover[e] 是基本回路经过 e 的非树边条数。
// 答案 = 1 + min cover[e],cover 用树上边差分(非树边给 u-v 路径 +1)统计。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 20005; // N <= 20000,留一点安全余量
const int MAXARC = 2 * MAXN; // 生成树邻接表:N-1 条树边 → 2(N-1) 条弧
const int LOG = 16; // 2^15 = 32768 > 20000,16 层足够且留一层余量
int head[MAXN], nxt[MAXARC], to[MAXARC], arcCnt; // 生成树的链式前向星
int par[MAXN], dep[MAXN]; // 以 1 为根:父亲与深度
int up[LOG][MAXN]; // 倍增祖先,up[0][x] = par[x]
ll diffCnt[MAXN]; // 树上边差分的累加数组
int order[MAXN]; // BFS 序,倒着扫就是自底向上
void addArc(int u, int v) {
to[arcCnt] = v;
nxt[arcCnt] = head[u];
head[u] = arcCnt++;
}
// 快读:最大输入约 10^6 条边(2×10^6 个数),fread 缓冲比 scanf 稳
const int BUFSZ = 1 << 16;
char buf[BUFSZ];
int bufLen = 0, bufPos = 0;
int readChar() {
if (bufPos == bufLen) {
bufLen = fread(buf, 1, BUFSZ, stdin);
bufPos = 0;
if (bufLen <= 0) return -1; // EOF
}
return buf[bufPos++];
}
// 本题所有输入都是非负整数,读到 EOF 就返回已累积的值
int readInt() {
int c = readChar();
while (c >= 0 && (c < '0' || c > '9')) c = readChar(); // 跳过空白与换行
int x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = readChar();
}
return x;
}
// u、v 的最近公共祖先(倍增法,本题 N 小,倍增足够)
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for (int k = 0; k < LOG; k++)
if (d >> k & 1) u = up[k][u];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--)
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
return up[0][u];
}
int main() {
ll T = readInt();
if (T < 0) T = 0;
while (T-- > 0) {
ll n = readInt(), m = readInt();
arcCnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = -1;
diffCnt[i] = 0;
}
for (int i = 0; i < n - 1; i++) { // 生成树 T 的 N-1 条边
int u = readInt(), v = readInt();
addArc(u, v);
addArc(v, u);
}
if (n <= 1) { // 退化输入:T 没有树边,不存在"恰好含一条 T 边"的割(约束外)
for (ll i = 0; i < m; i++) {
readInt();
readInt();
}
printf("0\n");
continue;
}
// 迭代 BFS 建树(链状树也不会爆栈),同时把倍增祖先预处理出来
int qh = 0, qt = 0;
order[qt++] = 1;
par[1] = 0;
dep[1] = 0;
for (int k = 0; k < LOG; k++) up[k][1] = 0;
while (qh < qt) {
int u = order[qh++];
for (int e = head[u]; e != -1; e = nxt[e]) {
int v = to[e];
if (v == par[u]) continue;
par[v] = u;
dep[v] = dep[u] + 1;
up[0][v] = u;
for (int k = 1; k < LOG; k++) up[k][v] = up[k - 1][up[k - 1][v]];
order[qt++] = v;
}
}
// 非树边:树上边差分,u-v 路径上所有树边 +1
ll extra = m - n + 1; // 题面:M-N+1 条不在 T 中的边
for (ll i = 0; i < extra; i++) {
int u = readInt(), v = readInt();
int w = lca(u, v);
diffCnt[u]++;
diffCnt[v]++;
diffCnt[w] -= 2;
}
// 逆 BFS 序做子树和:节点 x 累加后的值就是树边 (par[x], x) 的覆盖数
ll best = -1;
for (int idx = n - 1; idx >= 1; idx--) {
int x = order[idx];
ll c = diffCnt[x];
if (best < 0 || c < best) best = c;
diffCnt[par[x]] += c;
}
printf("%lld\n", best + 1);
}
return 0;
}复杂度
- 时间:每组
。C++ 版是 (每条非树边一次 的 LCA); Python 版建稀疏表 、每条非树边 ,同阶。按题面顶格数据 、 、 (合计 条边),C++ 版实测 problem10约ms, 远低于 ms 限时;Python 版同一测试点约 s(本题 Python 无需担心 TLE)。 - 空间:C++ 版
(倍增表 个 int,约MB); Python 版稀疏表约 个整数引用。两者都在 MB 之内。
总结
- 先给"合法割"定性,再谈算法:本题最容易卡住的地方不是数据结构,而是"恰好含一条树边"
这个条件的含义。想清楚"跨过割的树边唯一
割的两侧就是 的两个连通块", 问题立刻退化成"给每条树边数一数有多少非树边跨过它"。 - 把"跨过割"翻译成"基本回路经过":非树边
跨过 当且仅当 的基本回路含 , 于是一条边的覆盖数就有了两种等价视角,差分统计的合法性也来自这里。 - 树上差分是"多条路径
"的标准解法:端点 、LCA 、子树和还原, 这三步合起来是 的(不含 LCA 的 ),比"枚举每条树边再扫一遍非树边"的 快了一个量级。 - 答案下界是
:若某条树边是 的桥, ,最小割就是这条桥本身。 - 数据与题源说明:本题素材目录里带有数据生成脚本
data.py,说明data/的个测试点 是自造的(按题面上限分层生成:边界 → 小规模 → 顶格 → 多组顶格 ,树形状覆盖链 / 星 / 随机并含随机重标号);题面本身是网络重建版本, 与官方原题的措辞、数据强度可能不完全一致。目录里的 std.cpp是自研标程(其头注释也说明 未检索到公开题解),它与本题解互相印证:data/*.out就是std.cpp的产物, 本题解对个测试点逐点比对 一致;另外我还写了一份枚举全部二分的 暴力(不依赖本题结论)对 组 的随机小数据验证,同样全部一致。