UOJ#266 - [清华集训2016]Alice和Bob又在玩游戏

UOJ#266 - Click Here

  

Description

  Alice和Bob又在玩游戏。

  有$n$个节点,$m$条边($0 \leq m \leq n−1 $),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。

  Alice和Bob轮流操作(Alice 先手),每回合选择一个没有被删除的节点$x$,将$x$及其所有祖先全部删除,不能操作的人输。

  需要注意的是,树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。

  比如:1-3-2 这样一条链,1 号点是根节点,删除 1 号点之后,3 号点还是 2 号点的父节点。

  假设Alice和Bob都足够聪明,问Alice有没有必胜策略。

  

Input

  第一行一个正整数$T$,表示该测试点有$T$组数据;接下来$T$组数据。

  对于每组数据:

  输入第一行两个整数$n,m$,分别表示点数和边数(节点从$1$开始编号)。

  接下来$m$行,每行两个正整数$a,b$,表示节点$a$和节点$b$之间有一条边,输入数据中没有重边。

  

Output

  输出$T$行,每行输出Alice先手并且Alice和Bob都足够聪明的情况下谁获胜。

  对于$100\%$的数据,$1 \leq T \leq 10,1 \leq n \leq 10^5,\sum n \leq 2 \times 10^5,0 \leq m \leq n−1$,输入数据保证不会形成环,且每棵树的大小$\leq 5 \times 10^4$。

  

Solutions

  显然,每棵树都可以看做是一个独立游戏。因此,利用SG定理可将问题转换为求每棵树的SG函数。

  

  一个很暴力的做法是,枚举删除节点,那么会变成多棵子树的xor和,对所有情况求mex即为该树的SG函数。

  考虑优化这种做法。注意到,若将删除的节点限定在子树内的话,那么子树外的信息是不变的,而变化的信息恰好是该子树的所有变换情况

  若将该子树的变换情况看做一个集合的话,那么将该信息合并到原树,相当于对该集合内所有元素xor上其余子树的SG函数。

  

  换句话说,需要维护一个集合,支持整体xor上一个数,支持寻找mex,支持合并。

  这个可以用Trie实现。整体xor相当于在Trie上打标记;寻找mex相当于在Trie上贪心的往左走;合并则可以使用线段树合并的方法解决,其对时间的分析依旧成立。

  时间复杂度$O(n \, log \, n)$

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang