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
AC × 22
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