Submission #11375362


Source Code Expand

#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline bool Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e17;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 1005;
ll n;
vector<P> to;
vector<ll> done(10005);
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
P dfs(ll node,vector<vector<ll>> &g){
    done[node] = true;
    ll size = 0,p = 1;
    vector<ll> siz;
    for(ll v:g[node]){
        if (done[v]) continue;
        ll s,q;
        tie(s,q) = dfs(v,g);
        size += s;
        siz.push_back(s);
        p *= q;
        p %= MOD;
    }
    ll k = size+1;
    for(ll i:siz){
        p *= COM(size,i);
        p %= MOD;
        size -= i;
    }
    return P(k,p);
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    ll a,b;
    COMinit();
    rep(i,n-1){
        cin >> a >> b;
        --a;
        --b;
        to.push_back(P(a,b));
    }
    ll ans = 0;
    rep(i,n-1){
        rep(i,n) done[i] = false;
        tie(a,b) = to[i];
        vector<vector<ll>> g(n);
        ll x,y;
        rep(j,n-1){
            if (i == j) continue;
            tie(x,y) = to[j];
            if (x == b) x = a;
            if (y == b) y = a;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        ans += dfs(a,g).second;
        ans %= MOD;
    }
    PRINT(ans);
}

Submission Info

Submission Time
Task N - 木
User karudano
Language C++14 (GCC 5.4.1)
Score 5
Code Size 3034 Byte
Status AC
Exec Time 171 ms
Memory 512 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 9
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 AC 159 ms 512 KB
01 AC 71 ms 512 KB
02 AC 169 ms 384 KB
03 AC 170 ms 384 KB
04 AC 170 ms 384 KB
05 AC 171 ms 384 KB
06 AC 169 ms 384 KB
90 AC 1 ms 384 KB
91 AC 1 ms 384 KB