#line 1 "Main.cpp" #include #include #include #include #include #include #line 2 "nachia\\graph\\adjacency-list.hpp" #line 4 "nachia\\graph\\adjacency-list.hpp" #include namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyList(int n, const std::vector>& edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = v; if(rev) E[--buf[v]] = u; } I = std::move(buf); } AdjacencyList(const std::vector>& edges = {}){ int n = mn = edges.size(); std::vector buf(n+1, 0); for(int i=0; i targets, std::vector bounds){ AdjacencyList res; res.mn = bounds.size() - 1; res.E = std::move(targets); res.I = std::move(bounds); return res; } AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyList reversed_edges() const { AdjacencyList res; int n = res.mn = mn; std::vector buf(n+1, 0); for(int v : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u; int main(){ int N; cin >> N; vector> edges(N-1); rep(i,N-1){ int u,v; cin >> u >> v; u--; v--; edges[i] = {u,v}; } auto adj = nachia::AdjacencyList(N, edges, true); vector parent(N, -1); vector bfs = {0}; rep(i,N){ int p = bfs[i]; for(int e : adj[p]) if(parent[p] != e){ parent[e] = p; bfs.push_back(e); } } vector> dp(N); rep(i,N) dp[i][0] = 1; for(int i=N-1; i>=1; i--){ int p = bfs[i]; modint q1 = dp[p][0] + dp[p][1]; modint q0 = dp[p][1] + dp[p][2]; int pp = parent[p]; dp[pp][2] = dp[pp][2] * q0 + dp[pp][1] * q1; dp[pp][1] = dp[pp][1] * q0 + dp[pp][0] * q1; dp[pp][0] = dp[pp][0] * q0; } modint ans = dp[0][1] + dp[0][2]; cout << ans.val() << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;