fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. using namespace std;
  5. int const N=50001, mod=1e9+7;
  6. bool odw[N];
  7. long long il[N];
  8. double zm;
  9. pair<long long,long long>dp[N];
  10. vector<int>g[N];
  11.  
  12. void dfs(int v,int o){
  13.     odw[v]=1;
  14.     for(int i:g[v]){
  15.         if(odw[i]==0) {
  16.         	dfs(i,v);
  17.         	il[v]=il[v]*(dp[i].F+dp[i].S)%mod;
  18.         }
  19.     }
  20.     for(int i:g[v]){
  21.     	if(i!=o){
  22.     		zm=il[v]*dp[i].S;
  23. 	    	if(dp[i].F+dp[i].S!=0)	zm/=dp[i].F+dp[i].S;
  24. 	        dp[v].F=dp[v].F+zm;
  25. 	        dp[v].F%=mod;
  26.     	}
  27.     }
  28.     dp[v].S=il[v]%mod;
  29. }
  30.  
  31. int main(){
  32. 	ios_base::sync_with_stdio(0);
  33. 	cin.tie(0);
  34.     int n,m,a,b;
  35.     cin>>n>>m;
  36.     for(int i=1;i<=n;i++)   il[i]=1;
  37.     for(int i=0;i<m;i++){
  38.     	cin>>a>>b;  g[a].push_back(b);  g[b].push_back(a);
  39.     }
  40.     dfs(1,0);
  41.     //for(int i=1;i<=n;i++) cout<<dp[i].F<<' '<<dp[i].S<<endl;
  42.     cout<<(dp[1].F+dp[1].S)%mod;
  43. }
  44.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
7 6
1 2
1 3
1 4
3 5
3 6
6 7
stdout
copy 
17
https://ideone.com/2ngpFm
language:
C++ (gcc 8.3)
created:
283 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!