Submission #3717972

---

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;
static vector<int> dpf,dpg;
static vector<vector<int>> graph;
int n;
ll calcf(int num);
ll calcg(int num);
void input(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  graph.assign(n+1,vector<int>(n+1,0));
  int tmp1,tmp2;
  REP(i,n-1){
    cin >> tmp1 >> tmp2;
    graph[tmp1][tmp2] = graph[tmp2][tmp1] = 1;
  }
  dpf.assign(n+1,-1);
  dpg.assign(n+1,-1);
}
ll calcf(int num){
  if(dpf[num]!=-1) return dpf[num];
  dpf[num] = calcg(num);
  ll tmp = 1;
  for(int i=1;i<=n;i++) if(graph[num][i]){
    graph[i][num] = 0;
    tmp = tmp * calcg(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;
  for(int i=1;i<=n;i++) if(graph[num][i]){
    graph[i][num] = 0;
    dpg[num] = dpg[num] * calcf(i) % MOD;
  }
  return dpg[num];
}

int main(){
  input();
  cout << calcf(1) << endl;
}

Submission Info

Judge Result