连通块数 = 点数 - 边数,把 K_A-K_B 化成 Σ(2-d_i)x_i 的线性形式,博弈塌缩成按权值降序交替抢点。
OJ: roj
题目 ID: 1817
难度:提高
标签:数学贪心博弈python
创建: 2026-10-08 06:35
更新: 2026-10-08 06:35
形式化题目
给定一棵
记红点集的导出子图有
- 输入:第一行
,随后 行每行两个整数 表示一条边。 - 输出:一行一个整数,即最优博弈下的
。 - 数据范围:
;有 40% 的数据 ,另有 10% 的数据保证树是一条链。
题面【输入】写「接下来
行」是笔误: 个点的树只有 条边, 题面给出的两组样例也都是 行,因此按 条边读入。
正解
思路
朴素做法。 把染色过程直接当博弈树搜索:每个状态是「已染红的点集、已染蓝的点集、轮到谁」,
用 Alpha-Beta 或记忆化 minimax 从叶子往回推,叶子处再统计两个导出子图的连通块数。
状态数上界
瓶颈在哪? 顺着「树上问题」的惯性去写树形 DP 也会撞墙:一个点最终是红是蓝, 是由双方依次定点决定的全局结果,某个子树里红块的个数并不只取决于子树内部, 还取决于它与父节点是否同色、父节点是否被染,这需要记录极其复杂的边界连通性状态。
真正的问题是:我们把「动态博弈」和「图的拓扑」绑在一起看了。下面两步把这个耦合彻底拆开。
观察一:树导出子图的连通块数 = 点数 − 边数。 任意点集的导出子图必然是无环森林,
所以对森林都有「连通块数
则
观察二:把所有量都写成逐点线性形式。 给每个节点一个状态变量
于是
(两个指示函数都能用
代回目标:
这一步是全部关键:右边是
观察三:博弈塌缩成静态的降序抢数。 把权值固定为
也就是说:抢到一个点,不仅是自己拿到
- Alice 拿走最大的
,自己多 ; - Bob 拿走最大的
,让 Alice 拿不到那个 (而不是去拿一个无关紧要的小 )。
用交换论证可以确认这是最优的:设当前最大值是
实现上的化简:
整除的精确性。 式子里有个
两个样例手算。
代码
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-08 06:35
# update_at: 2026-10-08 06:35
import sys
# 抢点顺序的编码:权值 w = 2 - 度数 降序排好后,下标 0,2,4...(Alice 先手)取 +w,其余取 -w。
# 双方偏好一致,都是优先抢当前权值最大的点:抢到既得 +w,又让对手少得 -w,一进一出值 2w。
def optimal_difference(deg: list[int]) -> int:
"""按双方最优策略算 K_A - K_B:收益已被分解成逐点线性项,只需按权值大小轮流抢。"""
weights = sorted((2 - d for d in deg[1:]), reverse=True) # deg[0] 是占位格,切片跳过
# Σ w_i = 2n - 2(n-1) = 2 恒为偶数,任意加符号都不改奇偶,故整除精确(负数亦然)
return sum(w if i % 2 == 0 else -w for i, w in enumerate(weights)) // 2
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
deg = [0] * (n + 1) # deg[v] = 点 v 的度数,下标从 1 与题面点号对齐
edge_count = n - 1 # 题面写「接下来 N 行」是笔误,N 点树只有 N-1 条边
for _ in range(edge_count):
u, v = next(data), next(data)
deg[u] += 1
deg[v] += 1
print(optimal_difference(deg))
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-08 06:35
* update_at: 2026-10-08 06:35
*/
// 一本通 1817《染色游戏》(输入 N,随后 N-1 行边;题面写「N 行」是笔误,两组样例都只有 N-1 行)
//
// 核心恒等式:树的任意点集导出子图是森林,"连通块数 = 点数 - 边数",于是
// K_A - K_B = (|V_A| - |V_B|) - (|E_A| - |E_B|)。
// 记 x_i = +1 表示点 i 被 Alice 染红、-1 表示被 Bob 染蓝,d_i 为点 i 的度数,
// 逐边统计可得 |E_B| - |E_A| = -(1/2) * Σ_i d_i * x_i,而 |V_A| - |V_B| = Σ_i x_i,
// 合起来 K_A - K_B = (1/2) * Σ_i (2 - d_i) * x_i。
//
// 也就是说:每个点的贡献是独立线性的,只看它被谁抢到,权值 w_i = 2 - d_i,
// 抢的人拿 +w_i、对手拿 -w_i,而抢到一个点还等于从对手手里夺走它,双方都优先抢
// 当前权值最大的点,故答案 = (W_1 - W_2 + W_3 - W_4 + ...) / 2,W 为 w 的降序排列。
// 又 w_i = 2 - d_i,w 降序恰是 d 升序,实现里直接对度数排序。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
ll n; // 点数,题面上限 100000
ll deg[MAXN]; // deg[v] = 点 v 的度数;度数升序排列后其下标奇偶就是抢点的先后
int main() {
if (scanf("%lld", &n) != 1) return 0; // 防御性:空输入直接结束
for (ll i = 1; i < n; ++i) {
int u, v;
scanf("%d %d", &u, &v);
++deg[u];
++deg[v];
}
sort(deg + 1, deg + n + 1); // 度数升序 <=> 权值 2-deg 降序
ll sum = 0; // sum = Σ_奇数位 w - Σ_偶数位 w(此时 w 已按降序被取)
for (ll i = 1; i <= n; ++i) {
ll w = 2 - deg[i]; // 升序里下标小 => 度数小 => 权值大 => Alice 先抢
if (i & 1) sum += w; // 奇数轮由 Alice 抢走:得 +w
else sum -= w; // 偶数轮由 Bob 抢走:得 -w
}
// Σ_i w_i = 2n - 2(n-1) = 2 恒为偶数,任意改符号不改变奇偶性,故整除精确(负数亦然)
printf("%lld\n", sum / 2);
return 0;
}复杂度
- 时间:统计度数
,排序 ,交替求和 ,合计 。 时约 次基本操作,本机实测在毫秒级, ms 时限余量极大。 - 空间:只存
个度数, 个 int(约MB),远低于 MB。 中间量 , 位整数就够,C++ 里仍按惯例用 long long。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两种写法, 都用「度数升序 + 下标奇偶交替求和」,没有算法降级;Python 只需注意读入用sys.stdin.buffer.read().split()一次读完,级别的输入不会成为瓶颈。
总结
- 先化简目标函数,再谈博弈。
经「块数 点数 边数」和逐边代换后变成 ,博弈的耦合结构被彻底消掉——这是本题唯一的难点,代码只有几行。 - 能线性化的量不要留在组合结构里。把点数差、边数差都写成
的形式后, 树只剩下度数这一个参数;「谁和谁相邻」不再出现在答案里。 - 贡献对称化后,双方策略会重合。抢点的价值是
(自己得 且对手失 ), 两人都想抢权值大的点,动态博弈因此退化为一次排序。 与 反向单调,所以不用显式构造 ,直接给度数排序即可,少一个数组、少一次映射。 - 关于素材来源:本题所在素材包中带有数据生成脚本
data.py,即测试数据是依据题面自造的 (链、星、完全二叉树、随机树等分层),并非官方原题数据;题面本身与一本通 1817 一致, 两组样例与自造数据全部吻合,但出题意图与官方原题可能存在细微出入,特此注明。