[AtCoder] ARC 078 D: Fennec VS. Snuke

題目連結:http://arc078.contest.atcoder.jp/tasks/arc078_b

---

考慮一棵樹上的區域，其實有一塊是白的無法到達，一塊是黑的無法到達，另一塊則是大家都可以碰觸到。所以顯然在玩的時候一定是先搶大家都可以碰觸到的地方，會發現離自己越近的點越容易成為自己的顏色。仔細考慮後發現其實BFS一下，並且算個大家的領地大小就會是答案了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 100000 + 5;

vector<int> G[N];
bitset<N> visited;
int sum1=0, sum2=0;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int u, v;cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	queue<PII> BFS;
	BFS.push({1,1});BFS.push({n,2});
	visited[1]=1;visited[n]=1;
	while(!BFS.empty()){
		int cur=BFS.front().FF;
		int id=BFS.front().SS;
		BFS.pop();
		for(auto i:G[cur]){
			if(!visited[i]){
				visited[i]=1;
				BFS.push({i, id});
				if(id==1) sum1++;
				else sum2++;
			}
		}
	}
	cout<<((sum1>sum2)?"Fennec":"Snuke")<<'\n';
	return 0;
}