题目链接

题意简述

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

题解

$S G (i) = x o r (S G (s o n) + 1)$

代码

#include 
   
    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

转载地址：http://icwo.baihongyu.com/

你可能感兴趣的文章