結果
問題 | No.2377 SUM AND XOR on Tree |
ユーザー |
|
提出日時 | 2023-07-07 22:47:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 898 ms / 4,000 ms |
コード長 | 1,192 bytes |
コンパイル時間 | 4,400 ms |
コンパイル使用メモリ | 259,372 KB |
最終ジャッジ日時 | 2025-02-15 08:05:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;using ll = long long;using vll = vector<ll>;using vvll = vector<vll>;using mint = modint998244353;using vb = vector<bool>;using vvb = vector<vb>;using vvvb = vector<vvb>;#define rep(i,n) for(ll i=(ll)(0); i<(ll(n)); ++i)#define all(x) (x).begin(), (x).end()vll A;vvll G;vector<vector<mint>> P;void dfs(ll n, ll p, ll d) {if (A[n] & (1ll << d))P[n][1] = 1;else P[n][0] = 1;for (auto v : G[n]) {if (v != p) {dfs(v, n, d);mint a = P[n][0] * (P[v][0] + P[v][1]) + P[v][1] * P[n][1];mint b= P[n][1] * (P[v][0] + P[v][1]) + P[v][1] * P[n][0];P[n][1] = b;P[n][0] = a;}}}int main() {ll N;cin >> N;G.resize(N);rep(i, N - 1) {ll U, V;cin >> U >> V;U--; V--;G[U].push_back(V);G[V].push_back(U);}A.resize(N);rep(i, N)cin >> A[i];mint an = 0;rep(b, 31) {P.assign(N, vector<mint>(2, 0));dfs(0, -1, b);an += (P[0][1]*(1ll<<b));}cout << an.val() << endl;}