結果
問題 |
No.2377 SUM AND XOR on Tree
|
ユーザー |
![]() |
提出日時 | 2023-07-14 08:59:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 212 ms / 4,000 ms |
コード長 | 1,166 bytes |
コンパイル時間 | 1,133 ms |
コンパイル使用メモリ | 98,556 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-09-15 17:18:37 |
合計ジャッジ時間 | 6,546 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> using namespace std; #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vector<vector<int>> to(N); for (int e = 1; e < N; ++e) { int a, b; cin >> a >> b; --a, --b; to.at(a).push_back(b); to.at(b).push_back(a); } vector<int> A(N); for (auto &x : A) cin >> x; mint ret = 0; for (int d = 29; d >= 0; --d) { auto rec = [&](auto &&self, int now, int prv) -> pair<mint, mint> { mint dp0(0), dp1(0); if (A.at(now) & (1 << d)) dp1 = 1; else dp0 = 1; for (int nxt : to.at(now)) { if (nxt == prv) continue; const auto [ch0, ch1] = self(self, nxt, now); mint dp0nxt = dp0 * (ch0 + ch1) + dp1 * ch1; mint dp1nxt = dp0 * ch1 + dp1 * (ch0 + ch1); dp0 = dp0nxt; dp1 = dp1nxt; } return {dp0, dp1}; }; ret = ret * 2 + rec(rec, 0, -1).second; } cout << ret.val() << '\n'; }