読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

abc 036

algorithm algorithm-動的計画法 algorithm-深さ優先探索 contest contest-atcoder language language-c++11

d問題
abc036.contest.atcoder.jp

dfsとメモ再帰化でできる…はずだったのにlonglongとintを使い間違えて無事終了

#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 29
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll fact(ll a){ll b=1;FOR(i,1,a)b*=i;return b;}

struct Edge
{
  int src, dst;
  bool visit;
  Edge(int src, int dst) :
    src(src), dst(dst) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

Graph g;
vector<ll> dp;

ll dfs(int p, int s)
{
  if(dp[p] != -1) return dp[p];
  ll a1 = 1, a2 = 1;
  for(auto e : g[p]) if(e.dst != s)
    a1 = (a1*dfs(e.dst,p))%MOD;
  for(auto e1 : g[p]) if(e1.dst != s) for(auto e2 : g[e1.dst]) if(e2.dst != e1.src)
    a2 = (a2*dfs(e2.dst,e2.src))%MOD;
  dp[p] = (a1+a2)%MOD;
  return dp[p];
}

ll solve()
{
  dfs(0,-1);
  return dp[0];
}

int main()
{
  int n; cin >> n;
  g.resize(n);dp.resize(n);
  fill_n(dp.begin(),n,-1);
  REP(i,n-1)
  {
    int s, t; cin >> s >> t; s--; t--;
    g[s].push_back(Edge(s,t));
    g[t].push_back(Edge(t,s));
  }
  cout << solve() << endl;
  return 0;
}