【AtCoder078D】Fennec VS. Snuke

AtCoder Regular Contest 078 D - Fennec VS. Snuke

题意

给一个树，1是白色，n是黑色，其它没有颜色。Fennec每次可以染白色点的直接邻居为白色。Snuke则染黑色点的邻居为黑色。谁先不能动就输了。问谁赢。

题解

先找出1到n的唯一路径path[1..len]，然后Fennec可以依次取1到len/2的点及其不在路径上的孩子。剩下的就是Snuke的。谁多就谁赢了。

代码

#include <cstdio>
#define N 100005
int n;
struct edge{
    int to,next;
}e[N<<1];
int head[N],cnt;
void add(int u,int v){
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
int son[N];
int path[N],len;
bool dfs(int x,int fa){
    bool p=x==n;
    for(int i=head[x];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        p|=dfs(v,x);
    }
    son[fa]+=son[x]+1;
    if(p){
        path[++len]=x;
        return true;
    }
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    int ans=0;
    for(int i=len;i>len/2;--i)
        ans+=son[path[i]]-son[path[i-1]];
    printf("%s\n",ans*2>n?"Fennec":"Snuke");
    return 0;
}