题解 [牛客练习赛63 F] 牛牛的树行棋

• 牛牛的树行棋

题目描述

给定一棵树，树上每一个节点都有一枚棋子。

Alice 和 Bob 在这棵树上玩一个这样子的游戏 ：

Alice 和 Bob 轮流操作，每次把一枚棋子移动到其子树内的节点（显然一枚棋子在叶子节点就不能移动了），不能移动的人算输。

问 Alice 先手是否有必胜策略，若先手必胜，则求出第一步移动棋子的方案有多少种。

正解

这里先介绍一下 SG 函数（其实只需要知道结论就行）。

一个状态的 SG 函数值（后面简称 SG 值）是其所有后继状态（进行一次操作后所到达的状态） ---手动换行---

SG值 集合的 （最小不属于这个集合的非负整数，比如说 ）。

形式化的来说 。

结论 ：

1. 若当前局面的 SG 值为 0，先手必败，否则先手必胜。

2. 若一个游戏是多个独立游戏组成的，那么当前局面的 SG 值是多个独立游戏 SG 值的异或和 （就是 C++ 里面的 ^ 运算符）。

正题 :

对于这道题，对于每一枚棋子其实都是独立的。

也就是说，当前局面的多个独立游戏就是每一枚棋子，当前局面的 SG 值就是每一枚棋子的 SG 值的异或和。

那么一枚棋子的 SG 值怎么求呢？

若一枚棋子在叶子节点（后继状态是空集），它的 SG 值为 0。

若一枚棋子的后继节点只有叶子节点，它的 SG 值为 1。

若一枚棋子的后继节点 SG 值最大为 1 （那么肯定也有 0），它的 SG 值为 2。

若一枚棋子的后继节点 SG 值最大为 2 （那么肯定也有 1, 0），它的 SG 值为 3。

若一枚棋子的往子树内最多可以走 步，它的 SG 值为 。

可以通过一遍 dfs 得到所有棋子的 SG 值，进而得到当前局面的 SG 值，从而判断胜负。

那么怎么求方案呢？

注意到，只有 SG 值为 0 的局面是必败的，也就是说，第一次移动之后的局面 SG 值一定要等于 0。

考虑当前要移动的棋子为 ，它的 SG 值为 ，且令移动之前局面的 SG 值为 。

要使移动后 SG 值为 0，这枚棋子需要移动到 SG 值等于 的局面。

现在只需要求出树上每一个点子树内 SG 值的一个桶，就可以求出答案了。

具体怎么想怎么求就怎么求呗。

可以直接树差分或者长剖做到 ，亦或者用重剖做到 。

代码

这里安利一下 CYJian 的树差分代码。

然后还有我的辣鸡长剖代码。