Submission #2117216


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
 
using namespace std;
 
#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll 
typedef vector<int> vi;
typedef pair<int,int> pii;
 
vector<vi> v(100000);
int f[100000],g[100000];
 
 
void dfs(int p,int x){
  int i;
 
  rep(i,v[x].size())if(v[x][i]!=p) dfs(x,v[x][i]);
 
  f[x]=1;g[x]=1;
 
  rep(i,v[x].size())if(v[x][i]!=p){
    (g[x]*=f[v[x][i]])%=MOD;
    (f[x]*=g[v[x][i]])%=MOD;
  } 
  (f[x]+=g[x])%=MOD;
}
 
signed main(void) {
  int i,j;
  int n;
  cin>>n;
 
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    a--,b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
 
  dfs(-1,0);  
 
  cout<<f[0]<<endl;
}

Submission Info

Submission Time
Task D - 塗り絵
User rika0384
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1171 Byte
Status
Exec Time 83 ms
Memory 7808 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt
Case Name Status Exec Time Memory
000.txt 2 ms 2560 KB
001.txt 2 ms 2560 KB
002.txt 64 ms 6656 KB
003.txt 82 ms 7808 KB
004.txt 53 ms 6016 KB
005.txt 81 ms 7808 KB
006.txt 74 ms 7424 KB
007.txt 83 ms 7808 KB
008.txt 55 ms 6272 KB
009.txt 81 ms 7808 KB
010.txt 58 ms 6400 KB
011.txt 80 ms 7808 KB
012.txt 48 ms 5632 KB
013.txt 81 ms 7808 KB
014.txt 38 ms 4992 KB
015.txt 81 ms 7808 KB
016.txt 49 ms 5760 KB
017.txt 78 ms 7808 KB
018.txt 15 ms 3584 KB
019.txt 82 ms 7808 KB
020.txt 9 ms 3072 KB
021.txt 82 ms 7808 KB