fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int> g[1000000+10];
  6. long long mod = 1e9 + 7,dp[100000+10];
  7. long long tem;
  8.  
  9. long long dpsum(int n){
  10.     tem=0;
  11.  
  12.     for(int i=1;i<=n;i++){//make i=1 and add equality
  13.         tem = (tem + dp[i])%mod;
  14.     }
  15.     return tem;
  16. }
  17.  
  18. void dfs(int n,int p=-1){
  19.     dp[n]=1;
  20.  
  21.     for(int i=0;i<g[n].size();i++){
  22.         if(g[n][i] != p){
  23.             dfs(g[n][i],n);
  24.  
  25.             //increment dp[g[n][i]] by 1
  26.             tem = dp[g[n][i]]+1;
  27.             if(tem >= mod) tem -= mod;
  28.  
  29.             //use incremented dp[g[n][i]] and use % to calculate mod
  30.             dp[n] = (dp[n] * tem)%mod;
  31.         }
  32.     }
  33. }
  34.  
  35. int main(){
  36.     int t;
  37.     scanf("%d",&t);
  38.  
  39.     int v,x,y;
  40.     while(t--){
  41.         scanf("%d",&v);
  42.         for(int i=0;i<v-1;i++){
  43.             scanf("%d %d", &x , &y);
  44.             g[x].push_back(y);
  45.             g[y].push_back(x);
  46.         }
  47.  
  48.         dfs(v);
  49.         printf("%lld\n", dpsum(v));
  50.  
  51.         //clear the graph for next test case
  52.         for(int i=0;i<v+1;i++) g[i].clear();
  53.     }
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0.01s 15960KB
comments (?)
stdin
copy 
2
3
1 2
1 3
1
stdout
copy 
6
1
https://ideone.com/2YdpZq
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!