Advertisement
Josif_tepe

Untitled

May 16th, 2023
551
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. typedef long long ll;
  6. const int maxn = 300004;
  7. const ll MOD = 1e9 + 7;
  8. vector<int> graph[maxn];
  9. ll dp[maxn][2];
  10. void dfs(int node, int prev) {
  11.     dp[node][0] = 1; // 1 with white
  12.     dp[node][1] = 1; // 1 with black
  13.    
  14.     for(int i = 0; i < graph[node].size(); i++) {
  15.         int sosed = graph[node][i];
  16.         if(sosed == prev) continue;
  17.         dfs(sosed, node);
  18.         dp[node][0] *= (dp[sosed][0] + dp[sosed][1]) % MOD;
  19.         dp[node][1] *= dp[sosed][0] % MOD;
  20.         dp[node][0] %= MOD;
  21.         dp[node][1] %= MOD;
  22.                    
  23.                        
  24.     }
  25. }
  26. int main()
  27. {
  28.     ios_base::sync_with_stdio(false);
  29.     int n;
  30.     cin >> n;
  31.     for(int i = 0; i < n - 1; i++) {
  32.         int a, b;
  33.         cin >> a >> b;
  34.         a--; b--;
  35.         graph[a].push_back(b);
  36.         graph[b].push_back(a);
  37.     }
  38.     dfs(0, -1);
  39.     cout << (dp[0][0] + dp[0][1]) % MOD << endl;
  40.    
  41.     return 0;
  42. }
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement