Warning: session_start(): open(/tmp/sess_af8c3876b2dd785cd446fa2c8bc78342, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 团队 =====
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，维护当前子树中，对应高度的节点的数量，
对每个结点算一下就行了。