Submission #4330455
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, b; 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 >> b; a--; b--; edge[a].push_back(b); edge[b].push_back(a); } 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 = 0; i < n; i++) { fill(dp, dp+n, 0); P ret = dfs(i, -1); ans = (ans + ret.first) % MOD; } cout << ans / 2 << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | N - 木 |
User | veqcc |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1622 Byte |
Status | WA |
Exec Time | 2107 ms |
Memory | 384 KB |
Judge Result
Set Name | All | ||||||
---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 5 | ||||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | TLE | 2103 ms | 384 KB |
01 | WA | 41 ms | 384 KB |
02 | TLE | 2103 ms | 256 KB |
03 | TLE | 2103 ms | 384 KB |
04 | TLE | 2107 ms | 256 KB |
05 | TLE | 2103 ms | 384 KB |
06 | TLE | 2103 ms | 256 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |