无偏砍树游戏

Green Hackenbush是这样一个游戏：初始状态有一张无向图和一条虚线，称这条虚线为“地面”，起初所有点都与某一个地面上的点连通。两名玩家轮流从图中选出一条边删去，并移除此时所有分离于地面的部分。无法操作者（当一名玩家面对空图时）输。

称两个砍树图等价，如果它们的Sprague-Grundy函数值相等。

冒号法则：有三个砍树图 $G, H, K$ 。其中 $H$ 和 $K$ 都只有一个点在地面。取定 $G$ 上某个点 $x$ 。若 $H$ 和 $K$ 等价，则 $H$ 和 $G$ 关于 $x$ 的一点并 $G_x : H$ 和 $G_x : K$ 等价。

只需证如果 $H \oplus K$ 后手胜，则 $(G_x : H) \oplus (G_x:K)$ 后手胜：对于先手的一步操作，如果他操作的是 $H$ 或 $K$ ，按照 $H \oplus K$ 的必胜策略进行下一步操作即可。如果他操作的是某一个 $G$ ，则你在另一个 $G$ 上进行相同的操作。如果这次操作之后 $x$ 不再与地面相连，则上方的 $H$ 和 $K$ 会同时从图上脱离。之后完全模仿对方的操作即可。

由冒号法则，当砍树图是一个森林时，它的Sprague-Grundy函数可以从叶子开始递归地求出。且如果一个森林里边的个数为奇数，它的Sprague-Grundy函数值也是奇数。

如果 $G$ 的两个点 $u,v$ 边双连通，则可以把 $u$ 和 $v$ 融合得到一个图 $G_{u\sim v}$ ：它的顶点集为 $V(G) \backslash \{u, v\}\ \bigcup \ \{u\sim v\}$ 。 $V(G)\backslash\{u,v \}$ 里的边不变。如果一个 $u,v$ 以外的点和 $u,v$ 之间共连了 $k$ 条边，则新图里它和点 $u\sim v$ 也连 $k$ 条边。如果原图 $u,v$ 之间有 $a$ 条边， $u$ 和 $v$ 共有 $b$ 个自环，则新图里点 $u\sim v$ 连 $a+b$ 个自环。这样得到的新图顶点数减一，边数不变。

融合法则：如果两个点 $u,v$ 在同一个边双连通分支里，则 $G$ 和 $G_{u\sim v}$ 等价。

反证法，取一个极小的不满足融合法则的图 $G$ 。则 $G$ 只有一个点在地面上。设 $G_{u\sim v} \not \cong G$ 。如果 $G$ 中存在两个点在同一个边双 $G$ 连通分量里的点 $p,q$ ，且 $G_{p\sim q} \cong G$ 。则由 $G$ 的极小性 $G_{u\sim v}\cong G_{u\sim v,\ p\sim q} \cong G_{p\sim q} \cong G$ ，矛盾。

如果 $G$ 中有两个点 $u,v$ 在同一个边3连通分支中，考虑游戏 $G\oplus G_{u\sim v}$ 。设先手第一次砍的边是 $e$ ，你在另外一个图中把 $e$ 对应的边砍掉。这时候如果有子图从地面脱落，两个图脱落的部分一定相同。设这时候剩下的图为 $H$ ，则 $H$ 中 $u$ 和 $v$ 边双连通。再由 $G$ 的极小性，存在 $H\oplus H_{u\sim v}$ 的后手必胜策略。

如果 $G$ 有一个不经过地面的圈。将圈上的边删掉，圈上至多一个点与地面相连。设这个点是 $u$ ，则 $u$ 是 $G$ 的一个割点。考虑沿 $u$ 切开后的图，由冒号法则和 $G$ 的极小性知 $G$ 可以融合。

所以 $G$ 的圈都经过地面。如果 $G$ 包含多于一个圈，则 $G$ 可以分解成一些更小的恰包含一个圈的图的一点并。

所以只需要讨论 $G$ 是一个过地面的圈上长出一片森林的情况：

图中地面上两个点应该是同一个点

我们只需证明 $G$ 和把整个圈都缩成一个点的图等价就可以（因为如果你缩的是两个点 $u,v$ ，则 $G_{u\sim v}$ 是两个图关于 $u\sim v$ 这个点的一点并。对上面这个图用归纳假设，它可以缩成一个点，用冒号引理把他替换成一个森林然后再把下面的圈缩掉）。

由冒号引理，不妨设圈上每个点悬挂的都是一条链，设它们的长度分别为 $a_1, a_2, \cdots, a_m$ 。用 $(a_1, a_2, \cdots, a_m)$ 表示以 $a_1, a_2, \cdots, a_m$ 为格局的尼姆游戏。如果圈的长度是偶数，则只需证 $G \oplus (a_1, a_2, \cdots, a_m)$ 后手必胜。这个必胜策略可以直接构造：如果先手取的 $G$ 中链的部分或 $(a_1, a_2, \cdots, a_m)$ ，则后手在另外一边下模仿棋；如果先手取环上的边，则剩下一个奇数条边的森林，它的Sprague-Grundy函数值不等于零。

最后只剩下圈长为奇数的情况，此时 $G$ 缩圈之后得到一个格局为 $(a_1, a_2, \cdots, a_m)\oplus(1,1,\cdots,1)$ 的尼姆游戏，其中后面 $1$ 的个数是奇数。和偶数时不同的情况是先手可以取 $(1,1,\cdots,1)$ 的部分，所以只需证 $G\oplus(a_1, a_2, \cdots, a_m)$ 先手胜。我们证明先手可以砍掉圈上的一条边得到一个Sprague-Grundy函数为零的图。

拿这个图举例，砍掉虚线那条边之后剩下的森林的Sprague-Grundy函数值为 $(((((a+1)\oplus b)+1)\oplus c)+1)\oplus (x+1)$ 。我们希望它等于 $a\oplus b\oplus c\oplus x$ 。

将圈沿着地面上的点剪开，变成一条路，然后红蓝染色。如果一个顶点上长出的链长度为奇数，则它左右两边的边染同色；否则染异色。例如下面这张图：

对于颜色相同的连续一段，以它们的节点为根的树的大小都是奇数，设它们是 $(2b_1+1, 2b_2+1,\cdots, 2b_k+1)$ 。由于奇数异或奇数再加1相当于不管最低位而在剩下的数位取异或。所以这一串 $2b_i+1$ 连续异或加1相当于在除去最低位的其他数位连续异或。当遇到下一条颜色不同的线段时，假设节点上的值是 $2b_{k+1}$ ，则这个时候奇数异或 $2b_{k+1}$ 再加1会给高位带来加1的进位。所以我们可以把某种颜色的线段全部缩成一个点。

不妨设蓝色的线段有偶数条，将相邻的蓝色线段上节点的值异或在一起，然后把所有节点的值除2向下取整：

砍原图的某一条红边得到的森林的Sprague-Grundy函数的值右移一位等于砍新图里对应的红边的值。比较奇偶性可以得到最低位和所有节点全部异或起来的最低位相同。同时，由归纳假设，存在一条边使得砍掉它后新图的Sprague-Grundy函数值等于零，砍这条边就满足条件。