图删边博弈

Leasier · 2022-11-26 09:16:57 · 个人记录

众所周知我不会博弈论。

1. 树删边博弈

首先给出基本模型：

• 有一棵有根树，设其根为 R。
• 先后手轮流在树上删去一条边 u \to v，前提是删之前可以从 R 到达 v。若轮到某人时无法操作，此人失败。
• 博弈双方足够聪明。

我们依然考虑用 SG 函数来描述。

对于一条长为 n 的链，设其 SG 值为 SG(n)，则有：SG(n) = \operatorname{mex}_{i = 0}^{n - 1} SG(i)。类似于 Nim 游戏，可得：SG(n) = n。与此同时，我们也可以得到任意一个 SG 值为 x 的树都等价于一条长为 x 的链。

现在我们来考虑一棵树。假装我们已经知道了它所有子树的 SG 值，则我们将其子树全部视为链。

此时我们把儿子开头的若干条链分别加上当前这个根，则此时每条这样的链就是一个独立的新游戏了！

于是我们将所有儿子的 SG 值加一并异或起来即可得到当前子树的 SG 值。

dfs 即可。时间复杂度为 O(n)。

2. 图删边博弈

首先给出基本模型：

• 有一张有根无向图，设其根为 R。
• 先后手轮流在图上删去一条边 (u, v)，前提是删之前可以从 R 到达 u, v。若轮到某人时无法操作，此人失败。
• 博弈双方足够聪明。

对于一张一般的图，它比树究竟麻烦在哪里了呢？——有环！

• 对于一个偶环，删掉一条边后，一定会使边的数量变为奇数。这样两条单链的长度一定不相同，后续局面的 SG 值非 0。于是先手必败，偶环的 SG 值为 0。
• 对于一个奇环，删掉一条边后，一定会使边数变为偶数。我们需要讨论两种情况：
  • 若可以分出两条长度相同的链，则存在一个满足 SG 值为 0 的后续局面。
  • 若不能分出两条长度相同的链，由于两条链的长度差一定是偶数，其 SG 异或后也一定是偶数，所以不存在一个满足 SG 值为 1 的后续局面。

于是我们可以直接扔掉偶环，将奇环视为再连出去了一条边。

BCC 缩点即可转化为树删边的情况。时间复杂度为 O(n + m)，