結果
問題 | No.2377 SUM AND XOR on Tree |
ユーザー |
|
提出日時 | 2023-07-07 23:31:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,817 ms / 4,000 ms |
コード長 | 1,062 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 300,640 KB |
最終ジャッジ日時 | 2024-07-21 19:56:47 |
合計ジャッジ時間 | 46,804 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
N = int(input())G = [[] for _ in range(N)]for _ in range(N - 1):u,v = map(int,input().split())u -= 1v -= 1G[u].append(v)G[v].append(u)A = list(map(int,input().split()))P = 998244353ans = 0for i in range(30):dp = [[0] * 2 for _ in range(N)]stack = [(0,-1),(~0,-1)]while stack:now,parent = stack.pop()if now < 0:now = ~nowfor v in G[now]:if v != parent:stack.append((v,now))stack.append((~v,now))continueu = (A[now] >> i) & 1dp[now][u] = 1a = dp[now][0]b = dp[now][1]for v in G[now]:if v == parent:continuec = a * dp[v][0] + a * dp[v][1] + b * dp[v][1]d = a * dp[v][1] + b * dp[v][1] + b * dp[v][0]c %= Pd %= Pa = cb = ddp[now][0] = adp[now][1] = b#print(dp)ans += dp[0][1] * (1 << i)ans %= P#print(ans)print(ans)