Submission #11375289


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 0
Code Size 3033 Byte
Status TLE
Exec Time 2107 ms
Memory 54656 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 2
TLE × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 TLE 2107 ms 54656 KB
01 TLE 2103 ms 512 KB
02 TLE 2103 ms 1792 KB
03 TLE 2103 ms 1664 KB
04 TLE 2103 ms 1792 KB
05 TLE 2103 ms 1760 KB
06 TLE 2103 ms 1920 KB
90 AC 1 ms 384 KB
91 AC 1 ms 384 KB