海亮01/04博弈论杂题
T1
题意
有一棵 \(N\) 个节点的树，节点标号为 \(1,2,⋯,N\)，边用 \((x_i,y_i)\)表示。 Alice 和 Bob 在这棵树上玩一个游戏，Alice先手，两人轮流操作：
选择一条树上存在的边，把它断开使树变成两个连通块。然后把不包含 \(1\) 号点的联通块删除
当一个玩家不能操作时输，你需要算出：假如两人都按最优策略操作，谁将获胜。
题解
先考虑如果根只有一个子树怎么办？
显然一定是先手胜对叭？
如果是两个呢？
算一下两个子树的 SG 函数值，然后分成两个子游戏即可，最后异或一下就可以了。
但是三个呢？多个子树（\(k\) 个）呢？
发现我们可以将根克隆出 \(k\) 个出来，每一个都连接一个子树。然后发现这个东西将原来的游戏分成了 \(k\) 个子游戏，每个游戏的 SG 都是直接算出子树的 SG \(+1\) 得到的（加了一条边连向父亲对吧）。
然后就没了。
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10;
vector<int> edg[maxn];
int n;
int dfs(int u,int f){
int res = 0;
for(int v : edg[u])if(v != f)res ^= (dfs(v, u) + 1);
return res;
}
signed main(){
n = read();int u, v;
for(int i = 1;i < n;i++){
u = read(); v = read();
edg[u].push_back(v);edg[v].push_back(u);
}
puts(dfs(1, 0) ? "Alice" : "Bob");
return 0;
}