Submission #2661898
Source Code Expand
#include<bits/stdc++.h>
#define fr(i,n) for(int i=0;i<(n);++i)
#define foor(i,a,b) for(int i=(a);i<=(b);++i)
#define rf(i,n) for(int i=(n);i--;)
#define roof(i,b,a) for(int i=(b);i>=(a);--i)
#define all(x) x.begin(),x.end()
#define Sort(x) sort(all(x))
#define Reverse(x) reverse(all(x))
#define PQ priority_queue
#define print(x) cout<<(x)<<endl
using namespace std; typedef vector<int> vi;
typedef long long ll; typedef vector< ll> vl;
typedef unsigned long long ull; typedef vector<ull> vu;
typedef double dbl; typedef vector<dbl> vd;
typedef pair<int,int>pii; typedef vector<pii>vpii; typedef map<int,int>mii;
typedef pair< ll, ll>pll; typedef vector<pll>vpll; typedef map< ll, ll>mll;
typedef pair<dbl,dbl>pdd; typedef vector<pdd>vpdd; typedef map<dbl,dbl>mdd;
typedef pair< ll,int>pli; typedef vector<pli>vpli; typedef map< ll,int>mli;
typedef pair<dbl,int>pdi; typedef vector<pdi>vpdi; typedef map<dbl,int>mdi;
template<typename T>vector<T>&operator<<(vector<T>&v,const T t){v.push_back(t);return v;}
template<typename T>multiset<T>&operator<<(multiset<T>&m,const T t){m.insert(t);return m;}
template<typename T>set<T>&operator<<(set<T>&s,const T t){s.insert(t);return s;}
template<typename T,typename U>PQ<T,vector<T>,U>&operator<<(PQ<T,vector<T>,U>&q,const T t){q.push(t);return q;}
template<typename T,typename U>istream&operator>>(istream&s,pair<T,U>&p){return s>>p.first>>p.second;}
template<typename T>istream&operator>>(istream&s,vector<T>&v){fr(i,v.size()){s>>v[i];}return s;}
template<typename T,typename U>ostream&operator<<(ostream&s,const pair<T,U>p){return s<<p.first<<" "<<p.second;}
template<typename T>ostream&operator<<(ostream&s,const vector<T>v){for(auto a:v){s<<a<<endl;}return s;}
const int MD=1e9+7;
vpli dijkstra(const int N,const vpli E[],const int s,const ll inf){vpli d;fr(i,N)d<<pli{inf,i};d[s].first=0;PQ<pli,vpli,greater<pli>>pq;pq<<(d[s]=pli{0,s});while(pq.size()){pli a=pq.top();pq.pop();int v=a.second;if(d[v].first>=a.first){for(pli e:E[v]){if(d[v].first+e.first<d[e.second].first){d[e.second]=pli{d[v].first+e.first,v};pq<<pli{d[v].first+e.first,e.second};}}}}return d;}
ll gcd(const ll a,const ll b){return a?gcd(b%a,a):b;}
ll pow(const ll a,const ll n,const int m){ll t;return n?(n&1?a>=0?a%m:~-m+~a%m:1)*((t=pow(a,n>>1,m))*t%m)%m:1;}
ll C2(const int n){return(ll)n*~-n/2;}
vi ab[100001];
ll B[2][100001];
ll f(int p,int a,int c){
if(B[c][a])return B[c][a];
ll x=1;
for(int b:ab[a])if(b!=p){
x=x*(c*f(a,b,0)+f(a,b,1))%MD;
}
return B[c][a]=x;
}
main(){cin.tie(0);ios::sync_with_stdio(false);
int N;
cin>>N;
fr(i,N-1){
int a,b;
cin>>a>>b;
ab[a]<<b;
ab[b]<<a;
}
ab[0]<<1;
ab[1]<<0;
print((f(0,1,1)+f(0,1,0))%MD);
}
Submission Info
Submission Time |
|
Task |
D - 塗り絵 |
User |
x20 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2805 Byte |
Status |
AC |
Exec Time |
42 ms |
Memory |
7424 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
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 |
AC |
2 ms |
2560 KB |
001.txt |
AC |
2 ms |
2560 KB |
002.txt |
AC |
32 ms |
6400 KB |
003.txt |
AC |
42 ms |
7424 KB |
004.txt |
AC |
28 ms |
5760 KB |
005.txt |
AC |
42 ms |
7424 KB |
006.txt |
AC |
38 ms |
7040 KB |
007.txt |
AC |
42 ms |
7424 KB |
008.txt |
AC |
29 ms |
6016 KB |
009.txt |
AC |
42 ms |
7424 KB |
010.txt |
AC |
30 ms |
6016 KB |
011.txt |
AC |
42 ms |
7296 KB |
012.txt |
AC |
25 ms |
5504 KB |
013.txt |
AC |
42 ms |
7424 KB |
014.txt |
AC |
20 ms |
4864 KB |
015.txt |
AC |
42 ms |
7424 KB |
016.txt |
AC |
25 ms |
5504 KB |
017.txt |
AC |
42 ms |
7424 KB |
018.txt |
AC |
9 ms |
3456 KB |
019.txt |
AC |
42 ms |
7424 KB |
020.txt |
AC |
6 ms |
3072 KB |
021.txt |
AC |
42 ms |
7424 KB |