問題

D – 塗り絵

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

atcoder.jp

記録

• 2022/1/11 解法わからず。

解法

• 木DP。

コード例

#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;
}