Codeforces Bubble Cup X - Finals,E: Casinos and travel

http://codeforces.com/problemset/problem/852/E

初全方位木DPです。

観察するとGood Moodになる方法とBad Moodになる方法は同じ数だけあります。なのでGood Moodのみ考えれば良くて、
全方位木DPをすれば簡単に求められます。

全方位木DPについてですが、これは簡単で木から１つ子を除いた場合を考えて根からdfsするだけです。

int N;
vector<int> E[MAX_N];
ll g[MAX_N];
ll G[MAX_N];
int ts[MAX_N];

ll mod_pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}

ll invf(ll a) {
	return mod_pow(a, mod - 2);
}

ll dfs1(int v, int p) {
	ll res = 1;
	ts[v] = 1;
	bool found = false;
	rep(i, 0, sz(E[v])) {
		int n = E[v][i];
		if(n == p) continue;
		MUL(res, dfs1(n, v));
		ts[v] += ts[n];
		found = true;
	}
	if(!found) return g[v] = 1;
	else return g[v] = 2 * res % mod;
}

void dfs2(int v, int p, ll pv) {
	// debug(v, p, pv);
	G[v] = 2;
	rep(i, 0, sz(E[v])) {
		int n = E[v][i];
		if(n == p) MUL(G[v], pv);
		else MUL(G[v], g[n]);
	}
	rep(i, 0, sz(E[v])) {
		int n = E[v][i];
		if(n == p) continue;
		if(ts[n] == N - 1) dfs2(n, v, 1);
		else dfs2(n, v, G[v] * invf(g[n]) % mod);
	}
}

void solve() {
	cin >> N;
	if(N == 1) {
		cout << 1 << "\n";
		return;
	}
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b; a--; b--;
		E[a].pb(b);
		E[b].pb(a);
	}
	dfs1(0, -1);
	dfs2(0, -1, 1);
	ll ans = 0;
	// debug(vi(g, g + N));
	// debug(vi(G, G + N));
	rep(i, 0, N) ADD(ans, G[i]);
	cout << ans << "\n";
}

テストケースが12個しかないんですがこれは大丈夫なんですかね…