Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <array>
- #include <set>
- using namespace std;
- #define int long long
- const long long INF = 1e18 + 7;
- const int MAXN = 1e5 + 100;
- const int N = 1e5 + 10;
- const int MOD = 1e9 + 7;
- array<array<int, MAXN>, 2> dp;
- array<int, MAXN> used;
- vector<vector<int>> g;
- void dfs(int v, int p) {
- used[v] = true;
- int w = 1, b = 1;
- for (auto to: g[v]) {
- if (!used[to]) {
- dfs(to, v);
- }
- if (to != p) {
- w = ((dp[0][to] + dp[1][to]) % MOD * w) % MOD ;
- b = (b * dp[0][to]) % MOD;
- }
- }
- dp[0][v] = w;
- dp[1][v] = b;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- cin >> n;
- g.resize(n);
- for (int i = 0; i < n - 1; ++i) {
- int u, v;
- cin >> u >> v;
- --u, --v;
- g[u].emplace_back(v);
- g[v].emplace_back(u);
- }
- dfs(0, -1);
- cout << (dp[0][0] + dp[1][0]) % MOD;
- }
Advertisement
Add Comment
Please, Sign In to add comment