Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define debug(x) cout << #x << " = " << x << endl
- #define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
- #define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> ii;
- const int MAX = 1e3 + 5;
- const int MOD = 1e9 + 7;
- int n;
- vector<int> adj[MAX];
- int memo[MAX][2][2];
- int father[MAX];
- inline int add(int a, int b) {
- a += b;
- if(a >= MOD) {
- a -= MOD;
- }
- return a;
- }
- inline int mult(int a, int b) {
- return ((ll) a * b) % MOD;
- }
- int roll(int node, int my_color, int f_color) {
- if(node != 1 && (int) adj[node].size() == 1) {
- return my_color || f_color;
- }
- int &ans = memo[node][my_color][f_color];
- if(~ans) {
- return ans;
- }
- ans = 0;
- int prod = 1;
- int zero_prod = 1;
- for(auto &each : adj[node]) {
- if(each != father[node]) {
- father[each] = node;
- int v1 = roll(each, 0, my_color);
- int v2 = roll(each, 1, my_color);
- prod = mult(prod, add(v1, v2));
- zero_prod = mult(zero_prod, v1);
- }
- }
- ans = prod;
- if(f_color == 0 && my_color == 0) {
- ans = ans - zero_prod;
- if(0 > ans) {
- ans += MOD;
- }
- }
- return ans;
- }
- int main() {
- while(scanf("%d", &n) != EOF) {
- if(n == 1) {
- puts("1");
- continue;
- }
- fori(i, 1, n + 1) {
- adj[i].clear();
- }
- fori(i, 0, n - 1) {
- int u, v;
- scanf("%d %d", &u, &v);
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- memset(memo, -1, sizeof memo);
- father[1] = -1;
- printf("%d\n", add(roll(1, 0, 0), roll(1, 1, 0)));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement