結果
問題 |
No.2047 Path Factory
|
ユーザー |
![]() |
提出日時 | 2022-08-19 22:57:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 1,615 bytes |
コンパイル時間 | 4,338 ms |
コンパイル使用メモリ | 257,632 KB |
最終ジャッジ日時 | 2025-01-31 01:35:29 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using mint = atcoder::modint998244353; int main(){ int64_t N; cin >> N; vector<vector<int64_t>> edge(N); for(int64_t i = 0; i < N-1; i++){ int64_t u, v; cin >> u >> v; u--; v--; edge[u].push_back(v); edge[v].push_back(u); } vector<mint> dp1(N)/*親への遷移を切る*/, dp2(N)/*親への遷移を切らない*/; auto dfs = [&](auto &&self, int64_t vis, int64_t prv) -> void { for(auto nxt : edge[vis]){ if(nxt == prv) continue; self(self, nxt, vis); } if(vis != 0 and edge[vis].size() == 1){ dp1[vis] = 0; dp2[vis] = 1; }else{ vector<int64_t> child; for(auto c : edge[vis]) if(c != prv) child.push_back(c); int64_t csiz = child.size(); vector sub_count(3, vector(csiz, mint(0))); sub_count[0][0] = dp1[child[0]]; sub_count[1][0] = dp2[child[0]]; sub_count[2][0] = 0; for(int64_t i = 1; i < csiz; i++){ sub_count[0][i] = sub_count[0][i-1] * dp1[child[i]]; sub_count[1][i] = sub_count[1][i-1] * dp1[child[i]] + sub_count[0][i-1] * dp2[child[i]]; sub_count[2][i] = sub_count[2][i-1] * dp1[child[i]] + sub_count[1][i-1] * dp2[child[i]]; } dp1[vis] = sub_count[1][csiz-1] + sub_count[2][csiz-1]; dp2[vis] = sub_count[0][csiz-1] + sub_count[1][csiz-1]; } }; dfs(dfs, 0, -1); cout << dp1[0].val() << '\n'; return 0; }