hdu3094 A tree game

题目描述

题解：

树上删边。

$SG[u]$^=$SG[son[u]]+1$

代码：

#include<cstdio>
#include<cstring>
const int N = 100050;
template<typename T>
inline void read(T&x)
{
    T f = 1,c = 0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    x = f*c;
}
int T,n,hed[N],cnt;
struct EG
{
    int to,nxt;
}e[2*N];
void ae(int f,int t)
{
    e[++cnt].to = t;
    e[cnt].nxt = hed[f];
    hed[f] = cnt;
}
int dfs(int u,int f)
{
    int ret = 0;
    for(int to,j=hed[u];j;j=e[j].nxt)
        if((to=e[j].to)!=f)ret^=(dfs(to,u)+1);
    return ret;
}
int main()
{
    read(T);
    while(T--)
    {
        memset(hed,0,sizeof(hed));
        cnt=0;
        read(n);
        for(int f,t,i=1;i<n;i++)
        {
            read(f),read(t);
            ae(f,t),ae(t,f);
        }
        puts(dfs(1,0)?"Alice":"Bob");
    }
    return 0;
}