【AtCoder Grand Contest 017 D】Game on Tree | Mrsrz's blog

博弈论。

题目大意：

给定一棵树，以 $1$ 为根。双方轮流操作，每次选定一条边断掉，并扔掉和 $1$ 不在一个连通块里的点和边。不能操作者输。

问先手是否有必胜策略。

题解：

一棵树上面再加一个结点，一条边，其 sg 值加一。

一棵树的 sg 值是其所有子树 sg 值加一后的 xor 和。

推出整棵树的 sg 值即可。

Code：

#include<cstdio>
const int N=2e5+5;
struct edge{
    int to,nxt;
}e[N<<1];
int head[N],n,cnt;
int g(int u,int p){
    int r=0;
    for(int i=head[u];i;i=e[i].nxt)
    if(e[i].to!=p)r^=g(e[i].to,u)+1;
    return r;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    puts(g(1,0)?"Alice":"Bob");
    return 0;
}