wordpress 显示备案号/seo基本步骤

题目链接

https://agc017.contest.atcoder.jp/tasks/agc017_d

题意简述

现在有一棵树，Alice和Bob要玩一个游戏。Alice先手，他们轮流断开树上的一条边，并将不与$1$连接的连通块删去。如果轮到一个人操作时只剩一个点则判他负。问是否存在先手必胜策略。

题解

$$SG(i)=xor(SG(son)+1)$$

代码

#include <cstdio>int read()
{int x=0,f=1;char ch=getchar();while((ch<'0')||(ch>'9')){if(ch=='-'){f=-f;}ch=getchar();}while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}return x*f;
}const int maxn=100000;int n,pre[maxn*2+10],now[maxn+10],son[maxn*2+10],tot,f[maxn+10];int ins(int a,int b)
{pre[++tot]=now[a];now[a]=tot;son[tot]=b;return 0;
}int search(int u,int fa)
{for(int i=now[u]; i; i=pre[i]){int v=son[i];if(v==fa){continue;}search(v,u);f[u]^=(f[v]+1);}return 0;
}int main()
{n=read();for(int i=1; i<n; ++i){int a=read(),b=read();ins(a,b);ins(b,a);}search(1,0);puts(f[1]?"Alice":"Bob");return 0;
}