Submission #3692081

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;

vector<int> node;
vector<vector<int> > qq,q,nl;
void next(int a,int b,int k){
  node[a]=k;
  for(int i=0;i<qq[a].size();i++){
    if(qq[a][i]!=b){
      q[a].push_back(qq[a][i]);
      next(qq[a][i],a,k+1);
    }
  }
}


int main(){
  ll n;
  ll big=1000000000+7;
  cin>>n;
  qq.assign(n,vector<int>(0,0));
  q.assign(n,vector<int>(0,0));
  nl.assign(n,vector<int>(0,0));
  node.assign(n,0);
  vector<ll> f(n,0);
  vector<ll> g(n,0);
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    qq[a].push_back(b);
    qq[b].push_back(a);
  }
  next(0,0,0);
  for(int i=0;i<n;i++){
    nl[node[i]].push_back(i);
  }
  for(int i=n-1;i>=0;i--){
    for(int j=0;j<nl[i].size();j++){
      ll gg=1;
      ll hh=1;
      for(int l=0;l<q.at(nl.at(i).at(j)).size();l++){
        int d=q.at(nl[i][j])[l];
        gg=gg*f.at(d)%big;
        hh=hh*g.at(d)%big;
      }
      f.at(nl[i][j])=(gg+hh)%big;
      g.at(nl[i][j])=gg;
    }
  }
  cout<<(f[nl[0][0]])%big<<endl;
}

Submission Info

Judge Result