Submission #2969231

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using ll = long long;

constexpr int mod = 1e9 + 7;
constexpr int lim = 1e5;

bool visited[lim+1];
ll f[lim+1], g[lim+1];
int n;

class edge{
public:
  int to;
  edge(int t){
    to = t;
  }
};

class graph{
public:
  vector<vector<edge>> v;
  graph(int n){
    v.resize(n+1);
  }
};

void visit(const graph& gr, int v, int from){
  bool nxt = false;
  for(int i=0; i<gr.v[v].size(); i++){
    int to = gr.v[v][i].to;
    if(!visited[to]){
      visited[to] = true;
      nxt = true;

      visit(gr, to, v);
    }
  }

  if(nxt){
    f[v] = 1; g[v] = 1;
    for(int i=0; i<gr.v[v].size(); i++){
      int to = gr.v[v][i].to;
      if(to == from) continue;
      (g[v] *= f[to]) %= mod;
      (f[v] *= g[to]) %= mod;
    }

    (f[v] += g[v]) %= mod;
  }
}

ll solve(const graph& g){
  visited[1] = true;

  visit(g, 1, -1);

  return f[1];
}

int main(){
  cin >> n;
  graph gr(n);

  int a[n], b[n];
  for(int i=1; i<n; i++){
    cin >> a[i] >> b[i];
    gr.v[a[i]].push_back({b[i]});
    gr.v[b[i]].push_back({a[i]});
  }
  
  ll ans = solve(gr);

  cout << ans << endl;
 
  return 0;
}

Submission Info

Judge Result