题解 P8347 【「Wdoi-6」另一侧的月】

· · 题解

结论型博弈问题。

事实上我觉得确实没有紫色的难度。以下介绍的已经是一个真正能完整解决此问题的方法了。

首先我们考虑树比较小的情况。以下必胜必败都是在先手立场分析。

显然只有一个点时是必胜的，只有一条边时是必败的，有两条边时是必胜的。

当有三条边时，如果形成一条链那么是必胜的，如果形成菊花图那么是必败的。

如上我们分析一下必胜和必败的条件以及必胜策略的形式，容易发现结论：当且仅当所有点的度数均为奇数时先手必败。

以下证明此结论，记所有点的度数均为奇数的情况为 N 态，存在点度数为偶数的情况为 P 态。由博弈论的基本理论，我们只要证明 N 态的所有后继状态均为 P 态，且 P 态均存在一个后继状态为 N 态即可。

首先我们能够发现题目中的操作就是选一条边切断，后继状态为其中一边的子树。对于 N 态，我们假设切断的边为 (u,v)，则由于原树中 u,v 的度数均为奇数，因此切断后 u,v 的度数均为偶数，此时无论选择哪边的子树都存在一个点度数为偶数。

对于 P 态，由于至多只有有限个点度数为偶数，因此任意钦定一个根后必定有一棵子树中只有根节点的度数是偶数，此时选择这一棵子树作为后继状态，即为 N 态。

代码实现是容易的，不放代码了。