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 有没有必胜策略。
第一行包含一个正整数 $T$ ($1 \leq T \leq 10$)，表示该测试点有 $T$ 组数据。
对于每组数据，第一行包含两个非负整数 $n, m$ ($1 \leq n \leq 10^5; \sum n \leq 2 \times 10^5; 0 \leq m \leq n - 1$)，分别表示点数和边数 (节点从 $1$ 开始编号)。
接下来 $m$ 行，每行两个正整数 $a, b$ ($1 \leq a, b \leq n$)，表示节点 $a$ 和节点 $b$ 之间有一条边，输入数据中没有重边。
对于每组数据，输出一行一个字符串，表示 Alice 先手并且 Alice 和 Bob 都足够聪明的情况下谁获胜。
可以发现，游戏对森林中的每一棵树独立，因此，由 SG 定理，我们只需考虑每一棵树的 SG 值，然后将其异或起来即可。
接下来考虑计算一棵树的 SG 值。
我们采用 SG 函数的定义，它等于所有后继状态的 SG 值的 mex 值。
可以发现，它的每一个后继状态都是一个森林。那如何来求 mex 值呢？
先考虑删除根节点 $r$ 的情况，此时 SG 值为所有子树的 SG 值的异或和 $s_0$，这个不难维护。
若删除的不仅是 $r$，设它在以 $c$ 为根的子树 $C$ 中。则剩下的森林由$r$ 的子节点 ($c$ 除外) 的所有子树，以及在 $C$ 中的若干个子树。
发现后半部分是在求 $c$ 的 SG 函数时已经涉及到的子树。
因此，我们得到了：如果在求 $c$ 的时候，最终的 SG 值集合为 $A$ (从而 $\mathrm{SG}(c) = \mathrm{mex} \, A$)，则 $r$ 对应的集合应包含 $A$ 中每个元素异或上 "除 $c$ 外的所有子树的 SG 异或和" 的值。
对于每个 $c$，最终的集合都要包含这些元素，再算上 $s_0$，就是所得的最终集合 $R$。其中 $\mathrm{SG}(r) = \mathrm{mex} \, R$。
也就是说，我们需要实现这样一个数据结构：它能维护集合的加元素，以及一个集合异或上一个元素后与另一个集合合并。
这可以用可合并字典树来解决。合并的时候，就像线段树一样写就好了。
具体地，可以在每个点维护一个 val 信息，表示字典树中，以它为根的子树内部有几个互异元素，这样寻找 mex 值 (最小未出现值) 时就可以通过在字典树上二分解决。
其中异或上的元素，等于 "除 $c$ 外的所有子树的 SG 异或和"，于是可以用打标记的思想，给整棵字典树打一个标记 $tag$，表示它内部存储的 $x$，实际上表示 $x \oplus tag$。这样合并时只需异或上 $\mathrm{SG}(c)$ 即可，插入和询问的贪心时注意标记的影响。
总时间复杂度 $O \left( \sum n \log n \right)$。
#include <bits/stdc++.h>
const int N = 100010, M = N * 2, Z = N * 24;
int V, E, Es;
int to[M], first[N], next[M];
int cnt, root[N], sg[N], mask[N];
int d[Z][2], val[Z];
inline void addedge(int u, int v) {
to[++Es] = v; next[Es] = first[u]; first[u] = Es;
to[++Es] = u; next[Es] = first[v]; first[v] = Es;
}
void clear() {for (; cnt; --cnt) d[cnt][0] = d[cnt][1] = val[cnt] = 0;}
void insert(int t, int x) {
int b, ch;
for (b = 23; b >= 0; --b) {
++val[t]; ch = x >> b & 1;
t = (d[t][ch] ? d[t][ch] : d[t][ch] = ++cnt);
}
++val[t];
}
int merge(int t1, int t2, int offset, int b) {
if (!(t1 && t2)) return t1 | t2;
if (!~b) return val[t1] |= val[t2], t1;
int ch = offset >> b & 1;
d[t1][0] = merge(d[t1][0], d[t2][ch], offset, b - 1);
d[t1][1] = merge(d[t1][1], d[t2][ch ^ 1], offset, b - 1);
val[t1] = d[t1][0][val] + d[t1][1][val];
return t1;
}
int query_min(int t, int x) {
int b, ch, cur = 0;
for (b = 23; b >= 0; --b) {
if (!t) return cur << (b + 1);
ch = x >> b & 1;
val[d[t][ch]] < 1 << b ? (t = d[t][ch], cur = cur << 1) : (t = d[t][ch ^ 1], cur = cur << 1 | 1);
}
return cur;
}
void dfs(int x) {
int i, y; mask[x] = 0;
insert(root[x] = ++cnt, 0);
for (i = first[x]; i; i = next[i])
if (!root[y = to[i]]) {
dfs(y); mask[x] ^= sg[y];
root[x] = merge(root[x], root[y], mask[y] ^ sg[y], 23);
}
sg[x] = query_min(root[x], mask[x]);
}
void work() {
int i, u, v, ans = 0; Es = 0;
memset(first, 0, sizeof first);
scanf("%d%d", &V, &E);
for (i = 0; i < E; ++i) scanf("%d%d", &u, &v), addedge(u, v);
memset(root, 0, sizeof root);
for (i = 1; i <= V; ++i)
if (!root[i]) clear(), dfs(i), ans ^= sg[i];
puts(ans ? "Alice" : "Bob");
}
int main() {
int T;
for (scanf("%d", &T); T; --T) work();
return 0;
}
坑1：注意字典树合并时的深度参数，依据写法的不同而不同，比如，按照上面这种写法，要到 $-1$ 层后才到底层，才可以使用直接合并策略。