===== 团队 =====

2020.05.10: [[2019-hdu-multi-u-1|2019 Multi-University Training Contest 1]] ''pro: 8/9/13'' ''rk: 15/1105''

===== 个人 =====

==== zzh ====

2020.05.12 [[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1|Codeforces Round 641 (Div. 1)]] ''pro:4/7''

==== pmxm ====

==== jsh ====

  * 5/8 - 牛客练习赛63: ''pro: 5/6/6'' ''rk: 13/692''
  * 5/10 - Codeforces Round #641 (Div. 1): ''pro: 2/3/7'' ''rk: 932/1213''
  * 5/14 - Codeforces Round #642 (Div. 3): ''pro: 6/6/6'' ''rk: 170/16950''

详细：[[.:jiangshenghu:2020.05.08-2020.05.14 周报]]

===== 本周推荐 =====

==== zzh ====

[[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_432_div._1#f_rainbow_balls|Codeforces Round 432 (Div. 1): F. Rainbow Balls]]

[[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1#d_slime_and_biscuits|Codeforces Round 641 (Div. 1): D. Slime and Biscuits]]

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

==== jsh ====

=== 牛客练习赛63 - F - 牛牛的树行棋 ===

[[https://ac.nowcoder.com/acm/contest/5531/F|题目链接]]

== 题意 ==

一棵以 1 为根的树，树上每个节点都有一个棋子，两人轮流进行如下操作：
  * 选择某个不在叶子上的棋子
  * 将棋子移动到所在子树的任意某个节点上（除了棋子当前所在的节点）
轮流操作的过程中，节点上可以有多个棋子。

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

== 题解 ==

> 博弈论+树上的数据结构

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

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

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

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

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

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