結果
問題 | No.2377 SUM AND XOR on Tree |
ユーザー |
![]() |
提出日時 | 2023-06-10 22:40:39 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,073 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 81,900 KB |
実行使用メモリ | 300,804 KB |
最終ジャッジ日時 | 2024-07-06 23:47:48 |
合計ジャッジ時間 | 25,521 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 6 WA * 27 |
ソースコード
N=int(input())D=[[] for _ in range(N)]for i in range(N-1):x,y=map(int, input().split())x-=1;y-=1D[x].append(y);D[y].append(x)B=list(map(int, input().split()))mod=10**9+7E=[-1]*NE[0]=0from collections import dequed=deque()d.append(0)F={};FF=[];P=[-1]*Nwhile d:now=d.popleft()for nex in D[now]:if E[nex]==-1:E[nex]=E[now]+1v=E[nex]d.append(nex)P[nex]=nowif v not in F:F[v]=[]FF.append(v)F[v].append(nex)FF=sorted(FF)[::-1]ans=0for b in range(30):dp=[[0]*2 for _ in range(N)]for i in range(N):if (B[i]&(1<<b)):dp[i][1]=1else:dp[i][0]=1for f in FF:for now in F[f]:p=P[now]dpnew=[0,0]dpnew[0]+=dp[p][0]*dp[now][1]dpnew[1]+=dp[p][1]*dp[now][1]dpnew[0]+=dp[p][0]*dp[now][0]dpnew[0]+=dp[p][1]*dp[now][1]dpnew[1]+=dp[p][1]*dp[now][0]dpnew[1]+=dp[p][0]*dp[now][1]dpnew[0]%=moddpnew[1]%=moddp[p]=dpnewd=dp[0][1]%modans+=pow(2,b,mod)*dans%=modprint(ans)