fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5, MOD= 1e9+7;
  4. long long n, dp[MaxN][5];
  5. vector<long long> a[MaxN];
  6. void dfs(long long u, long long par)
  7. {
  8.     for (long long v : a[u])
  9.     {
  10.         if(v==par) continue;
  11.         dfs(v,u);
  12.         dp[u][1]=dp[u][1]*((dp[v][2]+dp[v][0])%MOD)%MOD;
  13.         dp[u][0]=dp[u][0]*((dp[v][1]+dp[v][2])%MOD)%MOD;
  14.         dp[u][2]=dp[u][2]*((dp[v][1]+dp[v][0])%MOD)%MOD;
  15.     }
  16. }
  17. void input()
  18. {
  19.     cin >> n;
  20.     for (long long i=1; i<n ;i++)
  21.     {
  22.         long long u,v;
  23.         cin >> u >> v;
  24.         a[u].push_back(v);
  25.         a[v].push_back(u);
  26.     }
  27. }
  28. void solve()
  29. {
  30.     memset(dp,0,sizeof(dp));
  31.     for (long long i=1; i<=n ;i++)
  32.     {
  33.         for (long long j=0; j<=2; j++)
  34.         {
  35.             dp[i][j]=1;
  36.         }
  37.     }
  38.     dfs(1,-1);
  39.     cout << ((dp[1][0]+dp[1][1])%MOD+dp[1][2])%MOD;
  40. }
  41. int main()
  42. {
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0);
  45.     input();
  46.     solve();
  47. }
  48.  
Success #stdin #stdout 0.01s 9692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UEMOU2
language:
C++14 (gcc 8.3)
created:
1 day 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!