Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug(x) cout << #x << " = " << x << endl
  4. #define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
  5. #define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef long double ld;
  11. typedef pair<int, int> ii;
  12.  
  13. const int MAX = 1e3 + 5;
  14. const int MOD = 1e9 + 7;
  15. int n;
  16. vector<int> adj[MAX];
  17. int memo[MAX][2][2];
  18. int father[MAX];
  19.  
  20. inline int add(int a, int b) {
  21.     a += b;
  22.     if(a >= MOD) {
  23.         a -= MOD;
  24.     }
  25.     return a;
  26. }
  27.  
  28. inline int mult(int a, int b) {
  29.     return ((ll) a * b) % MOD;
  30. }
  31.  
  32. int roll(int node, int my_color, int f_color) {
  33.     if(node != 1 && (int) adj[node].size() == 1) {
  34.         return my_color || f_color;
  35.     }
  36.     int &ans = memo[node][my_color][f_color];
  37.     if(~ans) {
  38.         return ans;
  39.     }
  40.     ans = 0;
  41.     int prod = 1;
  42.     int zero_prod = 1;
  43.     for(auto &each : adj[node]) {
  44.         if(each != father[node]) {
  45.             father[each] = node;
  46.             int v1 = roll(each, 0, my_color);
  47.             int v2 = roll(each, 1, my_color);
  48.             prod = mult(prod, add(v1, v2));
  49.             zero_prod = mult(zero_prod, v1);
  50.         }
  51.     }
  52.     ans = prod;
  53.     if(f_color == 0 && my_color == 0) {
  54.         ans = ans - zero_prod;
  55.         if(0 > ans) {
  56.             ans += MOD;
  57.         }
  58.     }
  59.     return ans;
  60. }
  61.  
  62. int main() {
  63.     while(scanf("%d", &n) != EOF) {
  64.         if(n == 1) {
  65.             puts("1");
  66.             continue;
  67.         }
  68.         fori(i, 1, n + 1) {
  69.             adj[i].clear();
  70.         }
  71.         fori(i, 0, n - 1) {
  72.             int u, v;
  73.             scanf("%d %d", &u, &v);
  74.             adj[u].push_back(v);
  75.             adj[v].push_back(u);
  76.         }
  77.         memset(memo, -1, sizeof memo);
  78.         father[1] = -1;
  79.         printf("%d\n", add(roll(1, 0, 0), roll(1, 1, 0)));
  80.     }
  81.  
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement