fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int const N=200001,mod=1e9+7;
  4. long long ods[N],sil[N],dp[N],zm;
  5. int roz[N];
  6. bool odw[N];
  7. vector<int>g[N];
  8.  
  9. long long dwu(int n, int k){
  10.     if(k>n) swap(n,k);
  11.     //cout<<sil[n+1]<<' '<<ods[k]<<' '<<ods[n-k+1]<<endl;
  12.     return ((long long)sil[n+1]*ods[k]%mod*ods[n-k+1])%mod;
  13. }
  14.  
  15. void dfs(int v){
  16.     odw[v]=1;
  17.     dp[v]=1;
  18.     for(int i:g[v]){
  19.         if(odw[i]==0){
  20.             dfs(i);
  21.             dp[v]=dp[v]*dp[i]%mod*ods[roz[i]]%mod;
  22.             //dp[v]=dwu(roz[v],roz[i])*dp[v]%mod*dp[i]%mod;
  23.             //cout<<i<<' '<<dwu(roz[v],roz[i])<<endl;
  24.             roz[v]+=roz[i];
  25.         }
  26.  
  27.     }
  28.     dp[v]=dp[v]*sil[roz[v]]%mod;
  29.     roz[v]++;
  30.     //cout<<v<<' '<<dp[v]<<endl;;
  31. }
  32.  
  33. long long pot(int base,int wyk){
  34. 	//cout<<base<<' '<<wyk<<endl;
  35.     if(wyk==0) return 1;
  36.     if(wyk==1) return base;
  37.     if(wyk%2==0){
  38.         zm=pot(base,wyk/2);
  39.         //cout<<(zm*zm)%mod<<endl;
  40.         return (zm*zm)%mod;
  41.     }
  42.     zm=(pot(base,wyk-1)*base)%mod;
  43.     //cout<<zm<<endl;
  44.     return zm;
  45. }
  46.  
  47. int main(){
  48. 	ios_base::sync_with_stdio(0);
  49. 	cin.tie(0);
  50.     int n,a,b;
  51.     cin>>n;
  52.     sil[0]=1;
  53.     ods[0]=1;
  54.     //cout<<pot(2,mod-2);
  55.     for(int i=1;i<=n;i++) {sil[i]=((long long)sil[i-1]*i)%mod; ods[i]=pot(sil[i],mod-2);}
  56.     for(int i=1;i<n;i++){
  57.         cin>>a>>b;
  58.         g[a].push_back(b);
  59.         g[b].push_back(a);
  60.     }
  61.     dfs(1);
  62.     cout<<dp[1];
  63. }
  64.  
Success #stdin #stdout 0.01s 12412KB
comments (?)
stdin
copy 
5
2 4
3 4
5 1
4 1
stdout
copy 
8
https://ideone.com/Hf6Gt1
language:
C++ (gcc 8.3)
created:
57 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!