Submission #5541998
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define fs first #define sc second #define mp make_pair #define pb push_back #define eb emplace_back #define ALL(A) A.begin(),A.end() #define RALL(A) A.rbegin(),A.rend() typedef long long LL; typedef pair<LL,LL> P; const LL mod=1000000007; const LL LINF=1LL<<60; const int INF=1<<30; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; vector<LL> fact; vector<LL> inver(200001); vector<int> v[1001]; LL combi(int n,int r){ if(n<r||n<0||r<0) return 0; return fact[n]%mod*inver[n-r]%mod*inver[r]%mod; } LL fpow(LL a, LL n){ LL x = 1; while(n > 0){ if(n&1){ x=x*a%mod; } a=a*a%mod; n >>= 1; } return x; } void set_combi(){ LL s=1; fact.push_back(1); for(int i=1;i<=200000;i++){ s*=i; s%=mod; fact.push_back(s); } inver[200000]=fpow(fact[200000],mod-2); for(int i=199999;i>=0;i--){ inver[i]=inver[i+1]*(i+1)%mod; } } P dfs(int u,int k,int l){ P ret = mp(1,0); for (int i = 0; i < v[u].size(); i++) { if(v[u][i]==k) continue; P p = dfs(v[u][i],u,l); ret.sc += p.sc; ret.fs = ret.fs*combi(ret.sc,p.sc)%mod*p.fs%mod; } ret.sc++; return ret; } int main(){ set_combi(); int n;cin >> n; for (int i = 0; i < n-1; i++) { int x,y;cin >> x >> y; x--,y--; v[x].pb(y); v[y].pb(x); } LL ans = 0; for (int i = 0; i < n; i++) { ans = (ans + dfs(i,-1,i).fs)%mod; } cout << ans*inver[2]%mod << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | N - 木 |
User | Yukly |
Language | C++14 (GCC 5.4.1) |
Score | 5 |
Code Size | 1682 Byte |
Status | AC |
Exec Time | 34 ms |
Memory | 4980 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 5 / 5 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 34 ms | 3956 KB |
01 | AC | 25 ms | 3956 KB |
02 | AC | 28 ms | 3956 KB |
03 | AC | 28 ms | 3956 KB |
04 | AC | 28 ms | 4980 KB |
05 | AC | 28 ms | 3956 KB |
06 | AC | 28 ms | 3956 KB |
90 | AC | 6 ms | 3956 KB |
91 | AC | 6 ms | 3956 KB |