P8347 「Wdoi-6」另一侧的月

给定一棵无根树，有两个人进行博弈，每轮游戏当前玩家会选择树中的一个节点，然后选择它的一棵子树，然后将树中除了这棵子树的其他部分全部删除。操作后只剩一个节点的人负。问谁有必胜策略。

\(2\le n\le 10^5\)

部分分：菊花图

题目给定的操作形式不是很优美，进行一些观察后发现：给树选择一个根，一次操作等价于要么保留一棵子树，要么删掉一棵子树。

考虑菊花图怎么做。如果一个玩家保留单独一个节点，那他就输了。因此两人只能轮流删除叶子。因此叶子数量是偶数时先手必胜，否则后手必胜。

考虑原图中的一棵菊花子树（即父亲方向不为空），如果它包含偶数个儿子，那么对这棵子树进行保留的玩家判负（因为后手变为先手）；如果是奇数（度数是偶数），那么保留这棵子树的玩家胜。因此，只要原图中存在一个度数为偶数的菊花子树，那么先手必胜。

考虑剩下的情况，所有 \(dep=2\) 的子树的度数都是奇数。此时，由于对这些子树进行保留操作的玩家负，可以把这些子树替换成单一一个节点，情况等价。因此可以归纳到 \(dep=3\) 的情况：如果存在一个 \(dep=2\) 的节点度数为偶数，或者根节点度数为偶数，那么先手必胜；说人话就是只要存在度数为偶数的节点，先手必胜。其余情况度数都为奇数，又可以简化为单个节点，因此可以归纳到 \(dep=4\) 的情况...

因此：只要图中存在一个偶数度点，那么先手必胜，否则后手必胜。因为先手可以找到一个最深的偶数度点（假设不是根），然后保留它；根据归纳假设，保留的子树是后手必胜的，因此原问题的先手必胜。如果只有根节点的度数是偶数，那么两人轮流删除根节点的子树，也是先手必胜。