fork(1) 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]=dwu(roz[v],roz[i])*dp[v]%mod*dp[i]%mod;
  22.             //cout<<i<<' '<<dwu(roz[v],roz[i])<<endl;
  23.             roz[v]+=roz[i];
  24.         }
  25.  
  26.     }
  27.     roz[v]++;
  28.     //cout<<v<<' '<<dp[v]<<endl;;
  29. }
  30.  
  31. long long pot(int base,int wyk){
  32. 	//cout<<base<<' '<<wyk<<endl;
  33.     if(wyk==0) return 1;
  34.     if(wyk==1) return base;
  35.     if(wyk%2==0){
  36.         zm=pot(base,wyk/2);
  37.         //cout<<(zm*zm)%mod<<endl;
  38.         return (zm*zm)%mod;
  39.     }
  40.     zm=(pot(base,wyk-1)*base)%mod;
  41.     //cout<<zm<<endl;
  42.     return zm;
  43. }
  44.  
  45. int main(){
  46. 	ios_base::sync_with_stdio(0);
  47. 	cin.tie(0);
  48.     int n,a,b;
  49.     cin>>n;
  50.     sil[0]=1;
  51.     ods[0]=1;
  52.     //cout<<pot(2,mod-2);
  53.     for(int i=1;i<=n;i++) {sil[i]=((long long)sil[i-1]*i)%mod; ods[i]=pot(sil[i],mod-2);}
  54.     for(int i=1;i<n;i++){
  55.         cin>>a>>b;
  56.         g[a].push_back(b);
  57.         g[b].push_back(a);
  58.     }
  59.     dfs(1);
  60.     cout<<dp[1];
  61. }
  62.  
Success #stdin #stdout 0.01s 13300KB
comments (?)
stdin
copy 
5
2 4
3 4
5 1
4 1
stdout
copy 
8
https://ideone.com/OtpqXf
language:
C++ (gcc 8.3)
created:
99 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!