AtCoder Regular Contest 078 D - Fennec VS. Snuke
题意
给一个树，1是白色，n是黑色，其它没有颜色。Fennec每次可以染白色点的直接邻居为白色。Snuke则染黑色点的邻居为黑色。谁先不能动就输了。问谁赢。
题解
先找出1到n的唯一路径path[1..len]，然后Fennec可以依次取1到len/2的点及其不在路径上的孩子。剩下的就是Snuke的。谁多就谁赢了。
代码
代码语言：javascript复制#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("%sn",ans*2>n?"Fennec":"Snuke");
return 0;
}
