Submission #4332853


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] * MOD(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 = MOD(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 3810 Byte
Status WA
Exec Time 309 ms
Memory 384 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 4
WA × 5
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 WA 303 ms 384 KB
01 WA 297 ms 384 KB
02 WA 308 ms 384 KB
03 WA 308 ms 384 KB
04 WA 308 ms 384 KB
05 AC 308 ms 384 KB
06 AC 309 ms 384 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB