ABC 036 D問題 塗り絵

木DPの問題でした。下のサイトが参考になりました（というより例題1がそのまま流用できた）
DP on Trees Tutorial - Codeforces

#include<iostream>
#include<vector>
using namespace std;
typedef long long int ll;
static const int MOD = 1e9 + 7;

vector<int> adj[100000];
ll f[100000], g[100000];

void dfs(int V, int pV){ // Vは始点となる頂点、pVは頂点Vの親とする
  ll product1 = 1, product2 = 1;

  for(auto v : adj[V]){
    if(v == pV) continue; // この文で、子から親への遷移を防ぐ
    dfs(v, V); // 子へと深さ優先探索を行う
    product1 *= f[v];
    product1 %= MOD;
    product2 *= g[v];
    product2 %= MOD;
  }

  g[V] = product1;
  f[V] = (g[V] + product2) % MOD;

  return ;
}

int main(){
  int N;
  cin >> N;
  fill(f, f + 100000, 0);
  fill(g, g + 100000, 0);
  for(int i = 1; i < N; i++){
    int u, v;
    cin >> u >> v;
    u--; v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfs(0, -1); //木の根を0とし、頂点の番号として使われていないものをpVとして探索を開始する

  cout << f[0] << endl;
  return 0;
}