Submission #4330374

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;
typedef pair<ll, int> P;

const ll MOD = 1000000007LL;
int n, a[1005], b[1005];
vector <int> edge[1005];
ll dp[1005], inv[1005], fac[1005], fiv[1005];

ll combination(int x, int y) {
    return fac[x] * fiv[y] % MOD * fiv[x-y] % MOD;
}

P dfs(int cur, int par) {
    dp[cur] = 1;

    int sz = 0;
    for (auto i : edge[cur]) {
        if (i == par) continue;

        P p = dfs(i, cur);
        sz += p.second;
    }

    int ret_sz = sz + 1;
    ll ret = 1LL;
    for (auto i : edge[cur]) {
        if (i == par) continue;

        P p = dfs(i, cur);
        ret = ret * p.first % MOD * combination(sz, p.second) % MOD;
        sz -= p.second;
    }

    return P(ret, ret_sz);
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> a[i] >> b[i];
        edge[a[i]].push_back(b[i]);
        edge[b[i]].push_back(a[i]);
    }

    inv[1]=fac[1]=fiv[1]=inv[0]=fac[0]=fiv[0]=1;
    for (ll i = 2; i <= n; i++) {
        fac[i] = fac[i-1] * i % MOD; // n!
        inv[i] = inv[MOD%i] * (MOD-MOD/i) % MOD; // n^-1
        fiv[i] = fiv[i-1] * inv[i] % MOD; // (n!)^-1
    }

    ll ans = 0LL;
    for (int i = 1; i < n; i++) {
        fill(dp, dp+n, 0);

        P ret1 = dfs(a[i], b[i]);
        P ret2 = dfs(b[i], a[i]);
        ans = (ans + ret1.first * ret2.first % MOD * combination(n-2, ret1.second-1) % MOD) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result