AGC 017D Game On Tree 博弈(Hackenbush删边)

题意:n个结点的树,Alice和Bob开始play,每次删除一条边,形成两连通分量,删除不包含1的那一个联通分量 不能操作的人算输,n<=1e5 Alice先手是否必胜? 参考 先考虑根结点只有一个分支时 SG(g)=SG(g')+1 要证明:g的后继状态的SG值为0~SG(g') 以树中结点个数作为阶段 归纳法证明  一个结点和两个结点显然成立, 去掉g-g'边得到SG(g)=0 去掉g'中的边 子树g'后继的SG为0~SG(g')-1,(包括g)最多有n-1个点,由归纳法SG(g)可以取1~SG(g')

综上SG(g)=SG(g')+1 .若根结点有多个分支,相当有nim中的每一堆异或即可. 

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; int n,f[N]; vector<int> e[N]; void dfs(int u,int fa) { f[u]=0; for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(v==fa) continue; dfs(v,u); f[u]^=(f[v]+1); } } int main() { while(cin>>n) { for(int i=1;i<=n;i++) e[i].clear(); int u,v; for(int i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs(1,0); if(f[1]) puts("Alice"); else puts("Bob"); } return 0; }