Submission #3962415

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
const ll MOD = 1e9+7;
vector<int> dpf,dpg;
vector<vector<int>> graph;
int n;
ll calcf(int num);
ll calcg(int num);
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
void input(){
  cin >> n;
  graph = vector<vector<int>>(n+1);
  int tmp1,tmp2;
  REP(i,n-1){
    cin >> tmp1 >> tmp2;
    graph[tmp1].push_back(tmp2);
    graph[tmp2].push_back(tmp1);
  }
  dpf.assign(n+1,-1);
  dpg.assign(n+1,-1);
}
void makegraph(int a,int b){ //親から子への有向グラフにする。a:child,b:parent
  if(a!=1){
    auto c = find(ALL(graph[a]),b);
    graph[a].erase(c);//aのリストからbを削除する。
  }
  REP(i,(int)graph[a].size()) makegraph(graph[a][i],a);
}
ll calcf(int num){
  if(dpf[num]!=-1) return dpf[num];
  dpf[num] = calcg(num);
  ll tmp = 1;
  REP(i,(int)graph[num].size()){
    tmp = tmp * calcg(graph[num][i]) % MOD;
  }
  dpf[num] = (dpf[num] + tmp) % MOD;
  return dpf[num];
}
ll calcg(int num){
  if(dpg[num]!=-1) return dpg[num];
  dpg[num] = 1;
  REP(i,(int)graph[num].size()){
    dpg[num] = dpg[num] * calcf(graph[num][i]) % MOD;
  }
  return dpg[num];
}

int main(){
  cioacc();
  input();
  makegraph(1,0);
  cout << calcf(1) << endl;
}

Submission Info

Judge Result