UOJ266. 【清华集训2016】Alice和Bob又在玩游戏(博弈论+01-trie)
题目大意
有 (n) 个节点，(m) 条边（(0 le m le n-1)），构成若干棵有根树，每棵树的根节点是该连通块内编号最小的点。
Alice 和 Bob 轮流操作（Alice 先手），每回合选择一个没有被删除的节点 (x)，将 (x) 及其所有祖先全部删除，不能操作的人输。
需要注意的是，树的形态是在一开始就确定好的，删除节点不会影响剩余节点父亲和儿子的关系。
比如：1-3-2 这样一条链，1 号点是根节点，删除 1 号点之后，3 号点还是 2 号点的父节点。
假设 Alice 和 Bob 都足够聪明，问 Alice 有没有必胜策略。
数据范围
对于(10 \%)的数据，(m=0);
对于(20 \%)的数据，(1 le n le 20);
对于(40 \%)的数据，(1 le n le 10^2)；
对于(60 \%)的数据，(1 le n le 10^3)；
对于(100 \%)的数据，(1 le T le 10, 1 le n le 10^5, sum{n} le 2 imes 10^5, 0 le m le n-1)，输入数据保证不会形成环，且每棵树的大小(le 5 imes 10^4)。
解题思路
首先可以看出这是一个博弈论问题，考虑用 SG 函数解决
如何算出一个子树的 SG 值？
枚举删除的第一个点 x，将根节点到 x 的路径删掉，发现树变成了森林，也就是当前局面的一个后继状态，那么森林中所有的树 SG 值异或起来插入集合中即可，最后对集合中的数取 (mex) 即可，时间复杂度 (Theta(N^2))
考虑数据结构优化
考虑一个子树向上合并的过程，发现只需将子树异或上其他子树的 SG 值并加入到集合，并加入删除根节点的 SG 值，也就是维护整体异或，合并，插入，不难发现可以用 01-trie 解决
代码
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;
template <typename T>
void read(T &x) {
x = 0; bool f = 0;
char c = getchar();
for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
for (;isdigit(c);c=getchar()) x=x*10+(c^48);
if (f) x=-x;
}
template<typename F>
inline void write(F x)
{
static short st[30];short tp=0;
if(x<0) putchar('-'),x=-x;
do st[++tp]=x%10,x/=10; while(x);
while(tp) putchar('0'|st[tp--]);
putchar('
');
}
template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }
template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }
const int N = 400500; int vis[N];
int tag[N*8], ch[N*10][2], cnt, n, m, T;
int siz[N*8], h[N], ne[N<<1], to[N<<1], tot;
inline void add(int x, int y) {
ne[++tot] = h[x], to[h[x] = tot] = y;
}
#define ls ch[x][0]
#define rs ch[x][1]
inline void spread(int x, int dep) {
if ((tag[x] >> dep) & 1) swap(ls, rs);
tag[ls] ^= tag[x], tag[rs] ^= tag[x];
tag[x] = 0;
}
void insert(int x, int p) {
int pp = p;
for (int i = 16;i >= 0; i--) {
int di = (x >> i) & 1; spread(p, i);
if (!ch[p][di]) ch[p][di] = ++cnt;
p = ch[p][di];
}
if (siz[p]) return; p = pp;
for (int i = 16;i >= 0; i--) {
int di = (x >> i) & 1;
p = ch[p][di]; siz[p]++;
}
}
int merge(int x, int y, int dep) {
if (!x || !y) return x | y;
if (dep == -1) return siz[x] = 1, x;
spread(x, dep), spread(y, dep);
ls = merge(ls, ch[y][0], dep - 1);
rs = merge(rs, ch[y][1], dep - 1);
siz[x] = siz[ls] + siz[rs];
return x;
}
int query(int x, int dep) {
if (!x) return 0; spread(x, dep);
if (siz[ls] >= (1 << dep)) return query(rs, dep - 1) + (1 << dep);
return query(ls, dep - 1);
}
int res[N], sg[N], Rt[N];
void dfs2(int x, int fa) {
vis[x] = 1, tag[x] = res[x] = 0, Rt[x] = x;
for (int i = h[x]; i; i = ne[i]) {
int y = to[i]; if (y == fa) continue;
dfs2(y, x); res[x] ^= sg[y];
}
insert(res[x], Rt[x]);
for (int i = h[x]; i; i = ne[i]) {
int y = to[i]; if (y == fa) continue;
tag[Rt[y]] ^= res[x] ^ sg[y];
Rt[x] = merge(Rt[x], Rt[y], 16);
}
sg[x] = query(Rt[x], 16);
}
void work(void) {
read(n), read(m); cnt = n, tot = 0;
memset(vis, 0, sizeof(vis));
memset(h, 0, sizeof(h));
memset(ch, 0, sizeof(ch));
memset(siz, 0, sizeof(siz));
for (int i = 1, x, y;i <= m; i++)
read(x), read(y), add(x, y), add(y, x);
int ans = 0;
for (int i = 1;i <= n; i++)
if (!vis[i]) dfs2(i, 0), ans ^= sg[i];
puts(ans ? "Alice" : "Bob");
}
int main() {
for (read(T); T--; ) work();
return 0;
}