前言
关于萌新刚学会SG函数而只会 \(O(n^2)\) 做法这件事。
题目
讲解
从易到难思考。
如果根节点只有一个儿子，这很好，先手砍掉这个点就能获胜。
如果根节点有两个儿子，那么率先到一个儿子状态的人获胜。然后递归看这两个儿子的游戏状态。
此时就已经可以用SG函数分析了，但显然萌新不太会证明，只会感性理解每个点的SG值为其所有儿子SG值+1的异或和。
因此只需要简单的dfs就可以完成这道题。
时间复杂度 \(O(n)\)。
代码
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot;
struct edge
{
int v,nxt;
}e[MAXN<<1];
void Add_Edge(int x,int y)
{
e[++tot] = edge{y,head[x]};
head[x] = tot;
}
void Add_Double_Edge(int x,int y)
{
Add_Edge(x,y);
Add_Edge(y,x);
}
int dfs(int x,int fa)
{
int ret = 0;
for(int i = head[x]; i ;i = e[i].nxt) if(e[i].v ^ fa) ret ^= dfs(e[i].v,x)+1;
return ret;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read();
for(int i = 1;i < n;++ i) Add_Double_Edge(Read(),Read());
printf(dfs(1,0) ? "Alice\n" : "Bob\n");
return 0;
}