AtCoder Regular Contest 078D: Fennec VS. Snuke

http://arc078.contest.atcoder.jp/tasks/arc078_b

解法自体は簡単だけど、バグらせたので。
こういう境界でバグらせやすい問題は[a b)の区間で考えるのがよさそう。
[a (a+b)/2)にすると半分、またはそれより1小さくなり、
[a (a+b+1)/2)にすると半分、またはそれより1大きくなる。

またwhileはカッコ内をループ内で主に注目する変数の存在条件にして、1進む処理をwhile文の一番下でやるのが良いだろう。
こうすればfor文と全く同じ形になる。
nextとnowを持って何かをするときはnextについて処理を行うことに注意しよう。dp的に考えたら当たり前のことだが。

vector<int> dep, tz;
vector<vector<int>> G;
vector<vector<int>> child;
vector<int> par;

int dfs(int v, int de = 0, int p = -1) {
	par[v] = p;
	dep[v] = de;
	ll res = 1;
	rep(i, 0, sz(G[v])) {
		int u = G[v][i];
		if(p == u) continue;
		child[v].push_back(u);
		res += dfs(u, de + 1, v);
	}
	return tz[v] = res;
}

void solve() {
	int N; cin >> N;
	dep.resize(N); tz.resize(N);
	G.resize(N);
	child.resize(N); par.resize(N);
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0);
	int v = N - 1;
	int f = (dep[N - 1] + 2) / 2, g = (dep[N - 1] + 1) / 2;
	rep(i, 0, sz(child[N - 1])) {
		int u = child[N - 1][i];
		g += tz[u];
	}
	while(par[v] != -1) {
		int uv = par[v];
		ll tmp = 0;
		rep(i, 0, sz(child[uv])) {
			int u = child[uv][i];
			if(u == v) continue;
			tmp += tz[u];
		}
		if(dep[uv] > (dep[N - 1] + 2) / 2 - 1) g += tmp;
		else f += tmp;
		v = uv;
	}
	/*
	rep(i, 0, N) debug(child[i]);
	debug(dep); debug(tz);
	debug(f, g);
	*/
	if(f > g) cout << "Fennec" << "\n";
	else cout << "Snuke" << "\n";
}