結果
問題 | No.2377 SUM AND XOR on Tree |
ユーザー |
![]() |
提出日時 | 2023-07-07 22:06:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 450 ms / 4,000 ms |
コード長 | 1,487 bytes |
コンパイル時間 | 1,931 ms |
コンパイル使用メモリ | 198,264 KB |
最終ジャッジ日時 | 2025-02-15 07:29:26 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int mod = 998244353; void mpl(int &x,int y) { x += y; if(x >= mod) x -= mod; } int f[100100]; int dp[100100][2]; void dfs(int n,int p,vector<vector<int>>&ki) { dp[n][f[n]] = 1; for(int i:ki[n]) { if(i == p) { continue; } dfs(i,n,ki); vector<int>tmp(2); for(int j = 0; j < 2; j++) { for(int k = 0; k < 2; k++) { if(k == 0) { mpl(tmp[j],1ll*dp[n][j]*dp[i][k]%mod); } else { mpl(tmp[j^1],1ll*dp[n][j]*dp[i][k]%mod); mpl(tmp[j],1ll*dp[n][j]*dp[i][k]%mod); } } } dp[n][0] = tmp[0]; dp[n][1] = tmp[1]; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<vector<int>>ki(N); for(int i = 0; i < N-1; i++) { int u,v; cin >> u >> v; u--; v--; ki[u].push_back(v); ki[v].push_back(u); } vector<int>A(N); for(int i = 0; i < N; i++) { cin >> A[i]; } int ans = 0; for(int i = 0; i < 30; i++) { for(int j = 0; j < N; j++) { f[j] = 1 & (A[j] >> i); for(int k = 0; k < 2; k++) { dp[j][k] = 0; } } dfs(0,-1,ki); mpl(ans,(1ll << i)*dp[0][1]%mod); } cout << ans << "\n"; }