染色游戏

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

连通块数 = 点数 - 边数,把 K_A-K_B 化成 Σ(2-d_i)x_i 的线性形式,博弈塌缩成按权值降序交替抢点。

OJ: roj

题目 ID: 1817

难度:提高

标签:数学贪心博弈python

创建: 2026-10-08 06:35

更新: 2026-10-08 06:35

形式化题目

给定一棵 NN 个节点的无向树 T=(V,E)T=(V,E),初始全部节点无颜色。Alice 先手,两人轮流每次选一个 未染色节点:Alice 把它染红,Bob 把它染蓝,直到 NN 个节点全部被染色(因此 Alice 恰好染 ⌈N/2⌉\lceil N/2 \rceil 个、Bob 恰好染 ⌊N/2⌋\lfloor N/2 \rfloor 个)。

记红点集的导出子图有 KAK_A 个连通块、蓝点集的导出子图有 KBK_B 个连通块。 Alice 想让 KA−KBK_A - K_B 尽可能大,Bob 想让 KA−KBK_A - K_B 尽可能小,双方均采取最优策略, 求最终的 KA−KBK_A - K_B。

  • 输入:第一行 NN,随后 N−1N-1 行每行两个整数 ui,viu_i, v_i 表示一条边。
  • 输出:一行一个整数,即最优博弈下的 KA−KBK_A - K_B。
  • 数据范围:N⩽100000N \leqslant 100000;有 40% 的数据 N⩽20N \leqslant 20,另有 10% 的数据保证树是一条链。

题面【输入】写「接下来 NN 行」是笔误:NN 个点的树只有 N−1N-1 条边, 题面给出的两组样例也都是 N−1N-1 行,因此按 N−1N-1 条边读入。

正解

思路

朴素做法。 把染色过程直接当博弈树搜索:每个状态是「已染红的点集、已染蓝的点集、轮到谁」, 用 Alpha-Beta 或记忆化 minimax 从叶子往回推,叶子处再统计两个导出子图的连通块数。 状态数上界 2N⋅N2^N \cdot N,N⩽20N \leqslant 20 的 40% 数据能过,N=105N = 10^5 完全不可行。

瓶颈在哪? 顺着「树上问题」的惯性去写树形 DP 也会撞墙:一个点最终是红是蓝, 是由双方依次定点决定的全局结果,某个子树里红块的个数并不只取决于子树内部, 还取决于它与父节点是否同色、父节点是否被染,这需要记录极其复杂的边界连通性状态。

真正的问题是:我们把「动态博弈」和「图的拓扑」绑在一起看了。下面两步把这个耦合彻底拆开。

观察一:树导出子图的连通块数 = 点数 − 边数。 任意点集的导出子图必然是无环森林, 所以对森林都有「连通块数 == 点数 −- 边数」。设

VA, VB=红点集、蓝点集,EA, EB=两端都红的边集、两端都蓝的边集, V_A,\ V_B = \text{红点集、蓝点集}, \qquad E_A,\ E_B = \text{两端都红的边集、两端都蓝的边集},

则 KA=∣VA∣−∣EA∣K_A = |V_A| - |E_A|,KB=∣VB∣−∣EB∣K_B = |V_B| - |E_B|,目标是

KA−KB=(∣VA∣−∣VB∣)−(∣EA∣−∣EB∣)=(∣VA∣−∣VB∣)+(∣EB∣−∣EA∣). K_A - K_B = \bigl(|V_A| - |V_B|\bigr) - \bigl(|E_A| - |E_B|\bigr) = \bigl(|V_A| - |V_B|\bigr) + \bigl(|E_B| - |E_A|\bigr).

观察二:把所有量都写成逐点线性形式。 给每个节点一个状态变量

xi={+1,节点 i 被 Alice 染红,−1,节点 i 被 Bob 染蓝. x_i = \begin{cases} +1, & \text{节点 } i \text{ 被 Alice 染红},\\ -1, & \text{节点 } i \text{ 被 Bob 染蓝}.\end{cases}

于是 ∣VA∣−∣VB∣=∑ixi|V_A| - |V_B| = \sum_i x_i。再看边:一条边两端同色时才进入 EAE_A 或 EBE_B, 异色时对 EAE_A、EBE_B 都不贡献。用 xx 写出来

[ (u,v) 同蓝 ]−[ (u,v) 同红 ]=(1−xu)(1−xv)−(1+xu)(1+xv)4=−xu+xv2. [\,(u,v) \text{ 同蓝}\,] - [\,(u,v) \text{ 同红}\,] = \frac{(1-x_u)(1-x_v) - (1+x_u)(1+x_v)}{4} = -\frac{x_u + x_v}{2} .

(两个指示函数都能用 xx 代数表达,异色时两项相消即得 00。)把每条边对 ∣EB∣−∣EA∣|E_B| - |E_A| 的贡献相加时, 每个 xix_i 恰好被累加了 did_i 次(did_i 为 ii 的度数),故

∣EB∣−∣EA∣=−12∑(u,v)∈E(xu+xv)=−12∑i=1Ndi xi. |E_B| - |E_A| = -\frac12 \sum_{(u,v) \in E} (x_u + x_v) = -\frac12 \sum_{i=1}^{N} d_i\, x_i .

代回目标:

  KA−KB=∑i=1Nxi−12∑i=1Ndixi=12∑i=1N(2−di) xi   \boxed{\;K_A - K_B = \sum_{i=1}^{N} x_i - \frac12\sum_{i=1}^{N} d_i x_i = \frac12 \sum_{i=1}^{N} (2 - d_i)\, x_i\;}

这一步是全部关键:右边是 NN 个互相独立的线性项,树的结构只通过每个点的度数 did_i 影响系数 wi=2−diw_i = 2 - d_i,与「谁和谁相邻」再无关系。博弈的最终得分只取决于 「每个点最终归谁」,也就是双方抢点的结果。

观察三:博弈塌缩成静态的降序抢数。 把权值固定为 wi=2−diw_i = 2 - d_i(它只由初始的树决定, 与博弈过程无关)。节点 ii 归 Alice 时代入 xi=+1x_i = +1,目标里出现 +wi+w_i; 归 Bob 时出现 −wi-w_i。于是一个点落到 Alice 手里还是 Bob 手里,对该点的贡献差是

(+wi)−(−wi)=2wi. (+w_i) - (-w_i) = 2w_i .

也就是说:抢到一个点,不仅是自己拿到 +wi+w_i,同时阻止了对手拿到 −wi-w_i, 一进一出价值 2wi2w_i。双方看到的「值得抢的程度」完全由 wiw_i 决定,而且价值越大的点, 对结果的边际影响越大。Alice 想让自己拿到的权值之和尽量大,Bob 想让 Alice 拿到的尽量小, 两人的偏好在这里完全一致——都是「优先拿走当前剩下权值最大的点」:

  • Alice 拿走最大的 ww,自己多 +w+w;
  • Bob 拿走最大的 ww,让 Alice 拿不到那个 +w+w(而不是去拿一个无关紧要的小 ww)。

用交换论证可以确认这是最优的:设当前最大值是 WW,若某玩家不去拿 WW 而拿了更小的 W′W', 则对手下一步必然拿走 WW(对手的最优策略同理),把这一步换成先拿 WW 不会更差。 于是双方轮流抢下 W1⩾W2⩾⋯⩾WNW_1 \geqslant W_2 \geqslant \dots \geqslant W_N(ww 的降序排列), Alice 拿到奇数位、Bob 拿到偶数位,答案就是

Ans=12(W1−W2+W3−W4+⋯ )=12(∑k 为奇Wk−∑k 为偶Wk). \text{Ans} = \frac{1}{2}\Bigl(W_1 - W_2 + W_3 - W_4 + \cdots\Bigr) = \frac{1}{2}\left(\sum_{k \text{ 为奇}} W_k - \sum_{k \text{ 为偶}} W_k\right).

实现上的化简:ww 降序排序等价于 dd 升序排序。 因为 wi=2−diw_i = 2 - d_i 是 did_i 的严格下降函数, 把 ww 从大到小排就是把它对应的 dd 从小到大排,所以代码里只需要给度数数组排序, 然后按下标奇偶交替加减即可,不必真的构造 ww 数组。

整除的精确性。 式子里有个 12\tfrac12,但不会有精度问题:所有点权值之和是定值

∑i=1Nwi=∑i=1N(2−di)=2N−2(N−1)=2, \sum_{i=1}^{N} w_i = \sum_{i=1}^{N}(2 - d_i) = 2N - 2(N-1) = 2 ,

22 是偶数,而把其中任意若干项的符号从 ++ 翻成 −- 只改变总和  mod 2\bmod 2 的 「偶 − 偶」形式,所以括号里的分子恒为偶数,整数除法(含负数)都是精确的。

两个样例手算。 N=4N=4 的星形树(样例 1):度数 3,1,1,13,1,1,1,权值 −1,1,1,1-1,1,1,1, 降序为 1,1,1,−11,1,1,-1,Ans=(1−1+1+1)/2=1\text{Ans} = (1-1+1+1)/2 = 1。 N=5N=5 的星形树(样例 2):度数 4,1,1,1,14,1,1,1,1,权值 −2,1,1,1,1-2,1,1,1,1, 降序为 1,1,1,1,−21,1,1,1,-2,Ans=(1−1+1−1−2)/2=−1\text{Ans} = (1-1+1-1-2)/2 = -1。都与题面一致。

代码

Python 版:

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++ 版(同一算法):

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-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;
}

复杂度

  • 时间:统计度数 O(N)O(N),排序 O(Nlog⁡N)O(N \log N),交替求和 O(N)O(N),合计 O(Nlog⁡N)O(N \log N)。 N=105N = 10^5 时约 1.7×1061.7 \times 10^6 次基本操作,本机实测在毫秒级,10001000 ms 时限余量极大。
  • 空间:只存 NN 个度数,O(N)O(N) 个 int(约 0.40.4 MB),远低于 256256 MB。 中间量 ∣sum∣⩽2(N−1)|\text{sum}| \leqslant 2(N-1),3232 位整数就够,C++ 里仍按惯例用 long long。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两种写法, 都用「度数升序 + 下标奇偶交替求和」,没有算法降级;Python 只需注意读入用 sys.stdin.buffer.read().split() 一次读完,10510^5 级别的输入不会成为瓶颈。

总结

  • 先化简目标函数,再谈博弈。KA−KBK_A - K_B 经「块数 == 点数 −- 边数」和逐边代换后变成 12∑(2−di)xi\tfrac12\sum (2-d_i)x_i,博弈的耦合结构被彻底消掉——这是本题唯一的难点,代码只有几行。
  • 能线性化的量不要留在组合结构里。把点数差、边数差都写成 ∑xi\sum x_i 的形式后, 树只剩下度数这一个参数;「谁和谁相邻」不再出现在答案里。
  • 贡献对称化后,双方策略会重合。抢点的价值是 2wi2w_i(自己得 +wi+w_i 且对手失 −wi-w_i), 两人都想抢权值大的点,动态博弈因此退化为一次排序。
  • ww 与 dd 反向单调,所以不用显式构造 ww,直接给度数排序即可,少一个数组、少一次映射。
  • 关于素材来源:本题所在素材包中带有数据生成脚本 data.py,即测试数据是依据题面自造的 (链、星、完全二叉树、随机树等分层),并非官方原题数据;题面本身与一本通 1817 一致, 两组样例与自造数据全部吻合,但出题意图与官方原题可能存在细微出入,特此注明。