题解：P6665 [清华集训 2016] Alice 和 Bob 又在玩游戏

Acheron_RBM · 2025-12-17 00:09:15 · 题解

首先，我们知道题目意思等价于：删除节点 x 及其祖先时，会移除 x 到根的路径；而原本附着在这条路径上的子树（被删除节点的子节点）会成为独立的新树。

而 Green Hackenbush on tree 的一次合法操作是：移除任意一条不与地面相连的线段，此时次线段以上的子树都会被移除。

我错了，但是真的是（数值）等价的，我是看代码等价就断言的。

首先考虑把原图的点换成边，边换成点，然后再把整棵树倒过来。

此时，若在原图中的操作为：删除节点 x 及其祖先，移除 x 到根的路径。

新图就是切断对应 x 这个点的边，对应 x 这个点的边上方部分（映射了 x 的祖先）删除，下面不动。

这样的一个新图可以根据下面的 Colon Principle 定理变成一个 bamboo，于是这两种游戏数值等价。

而 Green Hackenbush on tree 可以做到时间空间复杂度都是线性，本题自然可以。

所用定理我就不抄论文了，见 《Game Theory》 或者这个翻译。

然后我突然发现翻译讲的有点不清不楚的，我简述一下核心定理（Colon Principle）：

定义 bamboo 图为 Green Hackenbush on tree 图里面树退化成链的形态。

设 G 为一个 Green Hackenbush 图，节点 x \in V(G)。

设 H_1,H_2 为两棵树，且 \mathrm{SG}(H_1)=\mathrm{SG}(H_2)。

定义连接操作：

其中 r_H 为树 H 的根，边 (x,r_H) 将 H 附着到 x。

而定理内容是：

若 \mathrm{SG}(H_1)=\mathrm{SG}(H_2)，则

感性理解这个定理内容，实际上就是把一个树变成了一个链。

这个定理想要证明的是：一颗树 H 等价于一个长度为 SG(H)+1 的链。

根据 SG 函数的定义感性理解，由于 SG 函数是局面 mex，所以我们不关心树的具体形态结构，我们关心的是还有多少点可以切掉。

而对于一个 bamboo 图，他的 SG 函数值就是等于高度。