Luogu

UOJ

分析

考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。

于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。

如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。

如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG 函数值的异或和。

使用数据结构来维护，需要支持合并、整体异或、整体求 mex，01 Trie 可以胜任。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;
vector<int> E[N];

int ch[N*30][2],sz[N*30],tag[N*30];
int rt[N],tot=0;
int newnode() { ++tot; ch[tot][0]=ch[tot][1]=sz[tot]=tag[tot]=0; return tot; }
void pushup(int o) { sz[o]=sz[ch[o][0]]+sz[ch[o][1]]; }
void pushdown(int o,int d) {
    if (tag[o]) {
        if (tag[o]&(1<<d)) swap(ch[o][0],ch[o][1]);
        tag[ch[o][0]]^=tag[o],tag[ch[o][1]]^=tag[o],tag[o]=0;
    }
}
void insert(int &o,int w,int d) {
    if (!o) o=newnode();
    if (d<0) { sz[o]=1; return; }
    pushdown(o,d),insert(ch[o][w>>d&1],w,d-1),pushup(o);
}
int merge(int x,int y,int d) {
    if (!x||!y) return x+y;
    if (d<0) return x;
    pushdown(x,d),pushdown(y,d);
    ch[x][0]=merge(ch[x][0],ch[y][0],d-1);
    ch[x][1]=merge(ch[x][1],ch[y][1],d-1);
    pushup(x); return x;
}
int mex(int o,int d) {
    if (!o||d<0) return 0;
    pushdown(o,d);
    if (sz[ch[o][0]]<(1<<d)) return mex(ch[o][0],d-1);
    else return mex(ch[o][1],d-1)|(1<<d);
}

int sg[N],vis[N];
void dfs(int u,int fa) {
    vis[u]=1; int s=0;
    for (int v:E[u])
        if (v!=fa) dfs(v,u),s^=sg[v];
    insert(rt[u]=0,s,15);
    for (int v:E[u])
        if (v!=fa) tag[rt[v]]^=s^sg[v],rt[u]=merge(rt[u],rt[v],15);
    sg[u]=mex(rt[u],15);
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read();
        for (int i=1;i<=m;++i) {
            int u=read(),v=read();
            E[u].emplace_back(v),E[v].emplace_back(u);
        }
        int ans=0;
        for (int i=1;i<=n;++i) if (!vis[i]) dfs(i,0),ans^=sg[i];
        puts(ans?"Alice":"Bob");

        for (int i=1;i<=n;++i) E[i].clear(),vis[i]=0;
        tot=0;
    }
    return 0;
}