Submission #3692107

---

Source Code Expand

using ll=long long;
#include<limits>
namespace pcl{constexpr int INF=std::numeric_limits<int>::max()/2;constexpr ll LNF=std::numeric_limits<ll>::max()/2;constexpr double DNF=std::numeric_limits<double>::max()/2;constexpr double EPS=1e-8;constexpr int DX[]={1,0,-1,0,1,1,-1,-1};constexpr int DY[]={0,1,0,-1,-1,1,1,-1};}
#include<algorithm>
#include<cmath>
namespace pcl{template<typename T>void updmax(T&a,T const&b){a=std::max(a,b);}template<typename T>void updmin(T&a,T const&b){a=std::min(a,b);}template<typename T,typename U,typename V>bool in_range(T const&begin,U const&mid,V const&end){return begin<=mid&&mid<end;}template<typename T,typename U,typename V>bool in_range(T const&begin,std::initializer_list<U>list,V const&end){auto p=std::minmax_element(list.begin(),list.end());return begin<=*p.first&&*p.second<end;}inline bool eqdbl(double a,double b){return std::abs(a-b)<EPS;}inline bool ledbl(double a,double b){return a<b||eqdbl(a,b);}inline bool gtdbl(double a,double b){return a>b||eqdbl(a,b);}}
#ifdef PA_DEBUG
#define PD if(true)
#else
#define PD if(false)
#endif
#ifdef PA_DEBUG_LIB
#define PD_LIB if(true)
#else
#define PD_LIB if(false)
#endif
#include<iostream>
#include<vector>
namespace pcl{template<typename T>std::ostream&operator<<(std::ostream&os,std::vector<T>const&v){os<<'[';for(size_t i=0;i<v.size();i++){if(i!=0)os<<",";os<<v[i];}os<<']';return os;}template<typename T>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(size_t i=0;i<v.size();i++)is>>v[i];return is;}}
#include<type_traits>
#include<cmath>
#include<utility>
#include<vector>
namespace pcl{template<typename T>constexpr T gcd(T a,T b){return b==0?a:gcd(b,a%b);}template<typename T>constexpr T lcm(T a,T b){return a/gcd(a,b)*b;}template<typename T>constexpr T extgcd(T a,T b,T&xd,T&yd){if(b==0){xd=1,yd=0;return a;}T gcd=extgcd(b,a%b,yd,xd);yd-=(a/b)*xd;return gcd;}template<typename T>std::vector<T>sieve(T N){std::vector<T>result;std::vector<bool>is_not_prime(N);for(T i=2;i<=N;i++){if(is_not_prime[i])continue;result.push_back(i);for(T j=i+i;j<=N;j+=i)is_not_prime[j]=true;}return result;}template<typename T>constexpr T pow(T x,int n){T result=1;while(n>0){if(n&1)result*=x;x*=x;n>>=1;}return result;}template<typename T>constexpr bool is_prime(T val){for(T i=2;i<val;i++){if(val%i==0)return false;}return true;}}namespace pcl{template<typename T=ll,T MOD=1'000'000'007>class modint{private:T value;static inline T inv(T a){return inv_impl(a,MOD);}static T inv_impl(T a,T b){return(a==1?1:(1-b*inv_impl(b%a,a))/a+b);}public:modint():value(){}modint(modint const&init):value(init.value){}template<typename U>modint(U&&init):value(std::forward<U>(init)){if(value<0)value+=MOD;}explicit operator T()const{return value;}modint&operator+=(modint const&other){value+=other.value;if(value>=MOD)value-=MOD;return*this;}modint&operator-=(modint const&other){if(value<other.value)value+=MOD;value-=other.value;return*this;}modint&operator*=(modint const&other){value*=other.value;value%=MOD;return*this;}modint&operator/=(modint const&other){auto i=inv(other.value);*this*=i;return*this;}bool operator==(modint const&other)const{return value==other.value;}bool operator!=(modint const&other)const{return!(*this==other);}bool operator<(modint const&other)const{return value<other.value;}bool operator>(modint const&other)const{return other<*this;}bool operator<=(modint const&other)const{return*this<other||*this==other;}bool operator>=(modint const&other)const{return other<=*this;}modint&operator=(modint const&other){value=other.value;return*this;}modint&operator++(){value++;if(value==MOD)value=0;return*this;}modint&operator--(){if(value==0)value=MOD;value--;return*this;}};template<typename T,T MOD>modint<T,MOD>operator+(modint<T,MOD>lhs,modint<T,MOD>const&rhs){return lhs+=rhs;}template<typename T,T MOD>modint<T,MOD>operator-(modint<T,MOD>lhs,modint<T,MOD>const&rhs){return lhs-=rhs;}template<typename T,T MOD>modint<T,MOD>operator*(modint<T,MOD>lhs,modint<T,MOD>const&rhs){return lhs*=rhs;}template<typename T,T MOD>modint<T,MOD>operator/(modint<T,MOD>lhs,modint<T,MOD>const&rhs){return lhs/=rhs;}}
#include<bits/stdc++.h>
using namespace std;using namespace pcl;vector<int>calc_distance(vector<vector<int>>const&tree){vector<int>dist(tree.size(),-1);queue<pair<int,int>>que;que.push(make_pair(0,0));while(!que.empty()){int c,d;tie(c,d)=que.front();que.pop();if(dist[c]!=-1)continue;dist[c]=d;for(auto child:tree[c]){que.push(make_pair(child,d+1));}}return dist;}int main(){int N;cin>>N;vector<vector<int>>tree(N);for(int i=0;i<N-1;i++){int f,t;cin>>f>>t;tree[f-1].push_back(t-1);tree[t-1].push_back(f-1);}auto dist=calc_distance(tree);vector<vector<modint<>>>memo(2,vector<modint<>>(N,-1));function<modint<>(int,bool)>dfs=[&](int curr,bool parent_black){if(memo[(int)parent_black][curr]!=modint<>(-1)){return memo[(int)parent_black][curr];}modint<>when_white=1;for(auto child:tree[curr]){if(dist[child]>dist[curr])when_white*=dfs(child,false);}modint<>when_black=0;if(!parent_black){when_black=1;for(auto child:tree[curr]){if(dist[child]>dist[curr])when_black*=dfs(child,true);}}return memo[(int)parent_black][curr]=when_white+when_black;};cout<<(ll)dfs(0,false)<<endl;}

Submission Info

Compile Error

./Main.cpp:25:9: fatal error: 'bits/stdc++.h' file not found
#include<bits/stdc++.h>
        ^
1 error generated.