fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)(a).size()
  8. #define FILL(a,x) memset(a,x,sizeof(a))
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<int,int> ii;
  13.  
  14. const int MOD = 1000000007;
  15.  
  16. ll mod_pow(ll a, ll e){
  17. ll r = 1;
  18. while(e){
  19. if(e&1) r = r*a % MOD;
  20. a = a*a % MOD;
  21. e >>= 1;
  22. }
  23. return r;
  24. }
  25.  
  26. int main(){
  27. ios_base::sync_with_stdio(false);
  28. cin.tie(NULL); cout.tie(NULL);
  29.  
  30. int n;
  31. if(!(cin >> n)) return 0;
  32.  
  33. vector<vector<int> > g(n+1);
  34. FOR(i,1,n-1){
  35.     int u,v;
  36.     cin >> u >> v;
  37.     g[u].pb(v);
  38.     g[v].pb(u);
  39. }
  40.  
  41. // freq[d] = number of ordered pairs (u,v) whose distance is d
  42. vector<ll> freq(n,0);
  43. vector<int> dist(n+1);
  44. queue<int> q;
  45.  
  46. FOR(s,1,n){
  47.     FOR(i,1,n) dist[i] = -1;
  48.     while(!q.empty()) q.pop();
  49.     dist[s] = 0;
  50.     q.push(s);
  51.     while(!q.empty()){
  52.         int u = q.front(); q.pop();
  53.         for(int v : g[u]){
  54.             if(dist[v] == -1){
  55.                 dist[v] = dist[u] + 1;
  56.                 q.push(v);
  57.             }
  58.         }
  59.     }
  60.     FOR(v,1,n){
  61.         int d = dist[v];           // 0 <= d <= n-1 in a tree
  62.         freq[d]++;
  63.     }
  64. }
  65.  
  66. // precompute factorials and inverse factorials up to n-1
  67. vector<ll> fact(n), invfact(n);
  68. fact[0] = 1;
  69. FOR(i,1,n-1) fact[i] = fact[i-1]*i % MOD;
  70. invfact[n-1] = mod_pow(fact[n-1], MOD-2);
  71. for(int i=n-2;i>=0;--i) invfact[i] = invfact[i+1]*(i+1) % MOD;
  72.  
  73. // nCk with 0<=k<=N<=n-1
  74. auto C = [&](int N, int K)->ll{
  75.     if(K<0 || K>N) return 0;
  76.     ll res = fact[N] * invfact[K] % MOD * invfact[N-K] % MOD;
  77.     return res;
  78. };
  79.  
  80. // precompute C(n-1, i) and its inverses
  81. vector<ll> Cn1(n), invCn1(n);
  82. FOR(i,0,n-1){
  83.     Cn1[i] = C(n-1, i);
  84.     invCn1[i] = mod_pow(Cn1[i], MOD-2);
  85. }
  86.  
  87. // answer for days i = 0 .. n-1
  88. // E_i = sum_{L} freq[L] * C(n-1-L, i) / C(n-1, i)
  89. // all computations done modulo MOD
  90. vector<ll> ans(n);
  91. FOR(i,0,n-1){
  92.     ll numer = 0;
  93.     FOR(L,0,n-1){
  94.         if(n-1-L < i) break; // C(n-1-L,i)=0 for larger i
  95.         ll comb = C(n-1-L, i);
  96.         numer = (numer + freq[L] % MOD * comb) % MOD;
  97.     }
  98.     ans[i] = numer * invCn1[i] % MOD;
  99. }
  100.  
  101. FOR(i,0,n-1){
  102.     if(i) cout << ' ';
  103.     cout << ans[i];
  104. }
  105. cout << el;
  106.  
  107. return 0;
  108.  
  109. }
  110.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/312e3a
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!