题目描述

Fennec and Snuke are playing a board game.
On the board, there are N cells numbered 1 through N, and N−1 roads, each connecting two cells. Cell ai is adjacent to Cell bi through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.
Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored. Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell. More specifically, each player performs the following action in her/his turn:
Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.
Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.
A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.

Constraints
2≤N≤105
1≤ai,bi≤N
The given graph is a tree.

输入

Input is given from Standard Input in the following format:
N
a1 b1
:
aN−1 bN−1

输出

If Fennec wins, print Fennec; if Snuke wins, print Snuke.

样例输入

7
3 6
1 2
3 1
7 4
5 7
1 4

样例输出

Fennec

分析:本题最优策略是尽量堵住对手,BFS扫到最后发现谁占据的节点多,谁就会赢。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define range(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define rerange(i,a,b) for(int i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
int n,x,y,col[],cnt[];
vector<int> map[];
void init(){
cin>>n;
range(i,,n-){
cin>>x>>y;
map[x].push_back(y);
map[y].push_back(x);
}
col[]=,col[n]=;
}
void solve(){
queue<int>q;
q.push(),q.push(n);
while(!q.empty()){
int head=q.front();
q.pop();
++cnt[col[head]];
range(i,,map[head].size()-){
int tmp=map[head][i];
if(col[tmp])continue;
col[tmp]=col[head];
q.push(tmp);
}
}
cout<<(cnt[]<cnt[]?"Fennec":"Snuke")<<endl;
}
int main() {
init();
solve();
return ;
}

最新文章

  1. C#图片处理常见方法性能比较
  2. POJ 2965 The Pilots Brothers&#39; refrigerator
  3. C# 从CIL代码了解委托,匿名方法,Lambda 表达式和闭包本质
  4. [C++] C/C++结构体的区别
  5. Python中的join()函数split()函数
  6. 针对ASP.NET页面实时进行GZIP压缩优化的几款压缩模块的使用简介及应用测试!(附源码)
  7. ajax连接池和XMLHttpRequest
  8. sql server日期时间转字符串(转)
  9. ubuntu 10.04 下 samba 服务的配置
  10. Bandwidth内存带宽測试工具
  11. Windows下用Composer安装Laravel步骤(集成php环境用phpStudy2016版本)
  12. HTTP错误代码大全
  13. JNI的使用总结初篇
  14. 刨根问底HTTP和WebSocket协议
  15. (PMP)第2章-----项目运行环境
  16. Linux(lamp安装)
  17. ELK学习笔记之F5利用ELK进行应用数据挖掘系列(1)-HTTP
  18. 判断用户 是用的电脑还是手机 判断 是安卓还是IOS
  19. 【Beta阶段】第二次Scrum Meeting!
  20. stl string 使用(转载)

热门文章

  1. Linux系统自启动脚
  2. Python之print函数详解
  3. Redis实现之对象(三)
  4. Careercup - Microsoft面试题 - 4639756264669184
  5. Python+Selenium练习篇之2-利用ID定位元素
  6. Leetcode 502.IPO
  7. 【Luogu】P2468粟粟的书架(主席树+前缀和)
  8. [BZOJ1066][luogu_P2472][SCOI2007]蜥蜴
  9. FTB操作
  10. 各种 Python 实现的简单介绍与比较