Submission #4332817
Source Code Expand
#include <bits/stdc++.h>
#define int long long int
#define MOD(x) ((x % MOD_N) + MOD_N) % MOD_N
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,v) for(auto i=v.begin();i!=v.end();++i)
#define REACH(i,v) for(auto i=v.rbegin();i!=v.rend();++i)
#define LB(c,x) distance((c).begin(),lower_bound(ALL(c),x))
#define UB(c,x) distance((c).begin(),upper_bound(ALL(c),x))
#define COUNT(c,x) (lower_bound(ALL(c),x)-upper_bound(ALL(c),x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DEL(v) decltype(v)().swap(v)
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl;
#define NL cerr<<endl;
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T sum(vector<T>&v){return accumulate(ALL(v),T());}
template<typename T>T sum(vector<T>&v,int a,int b){return accumulate(v.begin()+a,v.begin()+b,T());}
template<typename T>T max(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T min(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T max_index(vector<T>&v){return distance((v).begin(),max_element(ALL(v)));}
template<typename T>T min_index(vector<T>&v){return distance((v).begin(),min_element(ALL(v)));}
struct edge { int to, cost; };
template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
const int INF = 1e18;
const int MOD_N = 1e9+7;
vector<int> frac;
void init_frac(int N) {
frac.resize(N+1);
frac[0] = 1;
for (int i = 1; i <= N; i++) {
frac[i] = MOD(frac[i-1] * i);
}
}
int powM(int x, int n) {
int res = 1;
while (n > 0) {
if ((n & 1) == 1) res = MOD(res * x);
x = MOD(x * x);
n >>= 1;
}
return res;
}
int inverseM(int x) {
return powM(x, MOD_N-2);
}
V<V<int>> G;
V<bool> used;
V<int> m, n;
void dfs(int i) {
used[i] = true;
n[i] = 0; m[i] = 1;
FOR(j, 0, G[i].size()) {
int to = G[i][j];
if (used[to]) continue;
dfs(to);
n[i] += n[to];
m[i] = MOD(m[i] * m[to] * inverseM(frac[n[to]]));
}
m[i] = MOD(m[i] * frac[n[i]]);
n[i] += 1;
}
int _dfs(int s) {
fill(ALL(used), false);
fill(ALL(m), -1);
fill(ALL(n), -1);
dfs(s);
return m[s];
}
signed main()
{
int N; cin >> N;
G.resize(N);
REP(i, N-1) {
int a, b; cin >> a >> b; a--; b--;
G[a].PB(b);
G[b].PB(a);
}
used.resize(N);
m.resize(N);
n.resize(N);
init_frac(N);
int ans = 0;
REP(i, N) {
ans += _dfs(i);
}
ans /= 2;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
N - 木 |
User |
habara_k |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3797 Byte |
Status |
WA |
Exec Time |
306 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 |
WA |
301 ms |
384 KB |
01 |
WA |
295 ms |
384 KB |
02 |
WA |
306 ms |
384 KB |
03 |
WA |
306 ms |
384 KB |
04 |
WA |
306 ms |
384 KB |
05 |
WA |
306 ms |
384 KB |
06 |
WA |
306 ms |
384 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |