【BZOJ4730】【清华集训2016】Alice和Bob又在玩游戏

标题真长

显然我们需要把每棵树的SG函数求出来

每棵树的SG函数为从树中对某个点进行操作剩下的所有子树的SG函数异或和的mex。

那么可以发现,每次要么是操作根节点,要么是操作儿子中的一个的子树内的点。

于是我们可以维护每棵树对子树内任意一个点操作得到的所有后继状态值的trie树(或者也可以叫线段树)

那么该树的SG值就是trie树中最小的未出现的数。

维护SG函数只要打标记整体异或以及合并就可以了

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz