TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

01 /
11
2022
 

塗り絵

問題

D – 塗り絵
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

int N;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> dp;

// 木DP
vector<int> dfs(int pos) {
  vector<int> result = {1, 1};
  visited[pos] = true;
  int n = graph[pos].size();
  rep(i, n) {
    if(visited[graph[pos][i]] == true) {
      continue;
    }
    vector<int> v = dfs(graph[pos][i]);
    result[0] = (ll)1 * result[0] * (v[0] + v[1]) % mod;
    result[1] = (ll)1 * result[1] * (v[0]) % mod;
  }
  return result;
}

int main() {
  cin >> N;

  graph.resize(N);
  visited.resize(N);
  dp.resize(2);

  rep(i, N - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  vector<int> ans = dfs(0);
  cout << (ans[0] + ans[1]) % mod << endl;
  return 0;
}