CVBB ACM Team

团队

都是比较有趣的一维随机游走题，虽然出题人/验题人把它放在 D 不知道是在想啥

一棵以 1 为根的树，树上每个节点都有一个棋子，两人轮流进行如下操作：

轮流操作的过程中，节点上可以有多个棋子。

询问先手是否能够必胜，同时，先手必胜的前提下，输出先手的第一步操作有多少种。

博弈论+树上的数据结构

容易发现对于每个棋子的游戏过程，都是独立、互不影响的组合游戏。由于是两个人轮流进行的多个游戏，我们只需要获得每个棋子对应的游戏的 SG，异或起来即为题目给定游戏的 SG。

对于一个棋子的游戏，子树除了自己的所有结点都能移动，容易得知 SG 即为子树的高度（离子树的根最远的节点的距离）。

这样我们就能得到当前游戏的 SG，答案的第一步就有了。

对于必胜前提下，先手的第一步操作，必然是要走到 SG 为 $0$ 的情况。记当前游戏的 SG 为 $g$。

对于节点 $u$ 为根的子树，记它的高度为 $h_u$。那么第一步如果是挪动 $u$ 节点上面的棋子，必然是要挪动到子树中高度为 $g \oplus h_u$ 的节点。只有这样才能使后手的局面的 SG 为 $0$。

对于快速地计算上面说的点对数量，我的做法是启发式合并（dsu on tree）。以高度为 key，维护当前子树中，对应高度的节点的数量，对每个结点算一下就行了。