結果
問題 | No.2377 SUM AND XOR on Tree |
ユーザー |
![]() |
提出日時 | 2023-06-29 08:36:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,170 ms / 4,000 ms |
コード長 | 1,529 bytes |
コンパイル時間 | 2,255 ms |
コンパイル使用メモリ | 210,596 KB |
最終ジャッジ日時 | 2025-02-15 03:01:45 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main() {constexpr ll mod = 998244353;int n; cin >> n;vector<vector<int>> tr(n);for(int i = 0; i < n-1; i++) {int u, v; cin >> u >> v; u--; v--;tr[u].push_back(v);tr[v].push_back(u);}vector<int> a(n);for(int i = 0; i < n; i++) cin >> a[i];ll ans = 0;for(int k = 0; k < 30; k++) {// dp[i][j]:=頂点jを根をする部分木で、根を含む連結成分のxorがivector<vector<ll>> dp(2, vector<ll>(n));vector<int> seen(n);vector<vector<int>> child(n);stack<int> stk;stk.push(~0);stk.push(0);while(!stk.empty()) {int u = stk.top(); stk.pop();if(u >= 0) {seen[u] = 1;for(int v : tr[u]) {if(seen[v]) continue;child[u].push_back(v);stk.push(~v);stk.push(v);}} else {u = ~u;dp[a[u]>>k&1][u] = 1;for(int v : child[u]) {tie(dp[0][u], dp[1][u]) = make_tuple((dp[0][u]*dp[0][v] + dp[0][u]*dp[1][v] + dp[1][u]*dp[1][v]) % mod,(dp[0][u]*dp[1][v] + dp[1][u]*dp[0][v] + dp[1][u]*dp[1][v]) % mod);}}}ans += dp[1][0] << k;}cout << ans % mod << endl;}