Submission #6423117

---

Source Code Expand

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
vector<int> G[1000];
const int MAX_N = 1000;
ll fact[MAX_N];
ll inv_fact[MAX_N];
ll mod_pow(ll a,ll n) {
	if (n == 0) return 1;
	if (n % 2 == 0) {
		ll tmp = mod_pow(a, n / 2);
		return (tmp*tmp) % MOD;
	}
	return a*mod_pow(a, n - 1) % MOD;
}
void comb_init(int n) {
	fact[0] = inv_fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = fact[i - 1] * i%MOD;
		inv_fact[i] = inv_fact[i - 1] * mod_pow(i, MOD - 2) % MOD;
	}
}
ll comb(int n, int k) {
	if (n < k) return 0;
	ll ret = fact[n];
	(ret *= inv_fact[k]) %= MOD;
	(ret *= inv_fact[n - k]) %= MOD;
	return ret;
}
P dfs(int v, int p) {
	vector<P> child;
	ll ret = 1;
	int sum = 0;
	for (int to : G[v]) {
		if (to == p) continue;
		child.push_back(dfs(to, v));
		(ret *= child.back().first) %= MOD;
		sum += child.back().second + 1;
	}
	int rest = sum;
	for (int i = 0; i < child.size(); i++) {
		(ret *= comb(rest, child[i].second + 1)) %= MOD;
		rest -= child[i].second + 1;
	}
	return P(ret, sum);
}
 int main() {
	 int N;
	 cin >> N;
	 vector<P> edge;
	 for (int i = 0; i + 1 < N; i++) {
		 int a, b;
		 cin >> a >> b;
		 a--; b--;
		 G[a].push_back(b);
		 G[b].push_back(a);
		 edge.emplace_back(a, b);
	 }
	 comb_init(N);
	 ll ans = 0;
	 for (P e : edge) {
		 P p1 = dfs(e.first, e.second);
		 P p2 = dfs(e.second, e.first);
		 int sum = p1.second + p2.second;
		 ll tmp = p1.first*p2.first%MOD;
		 (tmp *= comb(sum, p1.second)) %= MOD;
		 (ans += tmp) %= MOD;
	 }
	 cout << ans << endl;
}

Submission Info

Judge Result