夏晓光(loveJY)的博客

SG定理好题

首先一个树在经过一次删除操作后,会变成许多森林

然后这些森林其实就是原问题局面的一些子局面,那么不难记一个局面就是一个树,然后会发现不同的树之间的操作是不会产生影响的,所以我们把所有树的SG值异或起来,就可以计算出在这次操作之后子局面的SG值

同时由SG定理,原树的SG值就是所有不同删除操作之后得到的子局面的SG值的mex,所以我们就是要快速求出所有这样的SG值的mex

仔细想想,如果一次删除操作删在根,那么直接把根每个子树的SG值异或起来就能得到剩下的了

而如果删除操作在一颗子树内,那么把这棵子树外其他子树的SG值异或起来,再把这棵子树的操作完之后得到的SG集合都和那个值异或来转移

所以我们可以对于每棵子树记录一个SG集合表示子树内删除每个点后分别得到的后继SG值集合

然后我们需要一个全局异或,单点插入,快速合并以及支持查询全局mex的数据结构来维护

使用01trie即可,这样我们就能在$O(nlogn)$的时间内完成此题

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN = 5e5 + 7;
const int MAXM = 1e6 + 7;
const int MAXT = 5e6 + 7;
using namespace std;

int T, n, m, ccnt, ans;
int home[MAXN], nxt[MAXM], to[MAXM], vis[MAXN], rt[MAXN];
int sg[MAXN];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

const int up = 20;

namespace trie {
#define swap(x,y) (x^=y^=x^=y)
	int ls[MAXT], rs[MAXT], nd, siz[MAXT], tag[MAXT];
	inline void pushdown(int x, int dep) {
		if(tag[x]) {
			if(ls[x])tag[ls[x]] ^= tag[x];
			if(rs[x])tag[rs[x]] ^= tag[x];
			if(tag[x] & (1 << dep))swap(ls[x], rs[x]);
			tag[x] = 0;
		}
	}
	inline void pushup(int x) {
		siz[x] = siz[ls[x]] + siz[rs[x]];
	}
	inline void ins(int &x, int v, int dep = up) {
		if(!x)x = ++nd,
				  ls[nd] = rs[nd] = siz[nd] = tag[nd] = 0;
		if(dep == -1)return (void)(siz[x] = 1); //重复的只算一个
		pushdown(x, dep);
		if(v & (1 << dep))ins(rs[x], v, dep - 1);
		else ins(ls[x], v, dep - 1);
		pushup(x);
	}
	inline int merge(int x, int y, int dep = up) {
		if(!x || !y)return x | y;
		pushdown(x, dep);
		pushdown(y, dep);
		ls[x] = merge(ls[x], ls[y], dep - 1);
		rs[x] = merge(rs[x], rs[y], dep - 1);
		if(dep != -1)pushup(x);
		return x;
	}
	inline int query(int x, int dep = up) {
		if(!x)return 0;
		if(siz[ls[x]] < (1 << dep))return query(ls[x], dep - 1);
		else return query(rs[x], dep - 1) | (1 << dep);
	}
};
using namespace trie;

inline void init() {
	nd = 0;
	memset(rt, 0, sizeof(rt));
	memset(home, 0, sizeof(home));
	memset(vis, 0, sizeof(vis));
	ans = 0;
	ccnt = 0;
}

inline void dfs(int u, int F) {
	vis[u] = 1;
	int S = 0;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
		S ^= sg[v];
	}
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		tag[rt[v]] ^= (S ^ sg[v]);
		rt[u] = merge(rt[u], rt[v]);
	}
	ins(rt[u], S);
	sg[u] = query(rt[u]);
	return ;
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		init();
		scanf("%d%d", &n, &m);
		for(int i = 1, x, y; i <= m; ++i) {
			scanf("%d%d", &x, &y);
			ct(x, y);
			ct(y, x);
		}
		for(int i = 1; i <= n; ++i)
			if(!vis[i]) {
				dfs(i, 0);
				ans ^= sg[i];
			}

		if(ans)
			printf("Alice\n");
		else printf("Bob\n");
	}
	return 0;
}