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