結果
問題 | No.2949 Product on Tree |
ユーザー |
![]() |
提出日時 | 2024-10-25 21:54:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 689 ms / 2,000 ms |
コード長 | 741 bytes |
コンパイル時間 | 498 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 128,516 KB |
最終ジャッジ日時 | 2024-10-25 21:55:15 |
合計ジャッジ時間 | 30,127 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
n=int(input()) a=list(map(int,input().split())) e=[[] for i in range(n)] for i in range(n-1): u,v=map(int,input().split()) u-=1 v-=1 e[u]+=[v] e[v]+=[u] M=998244353 i2=pow(2,M-2,M) u=[0]*n v=[0]*n q=[0] ans=0 while len(q)>0: s=q[-1] if v[s]==0: v[s]=1 for t in e[s]: if v[t]==0: q+=[t] else: f=0 for t in e[s]: if v[t]==0: f=1 u[s]+=u[t]*a[s] u[s]%=M u[s]+=a[s] u[s]%=M ans+=u[s] ans%=M a2=0 for t in e[s]: if v[t]==0: a2+=u[t] a2%=M a2=a2**2 for t in e[s]: if v[t]==0: a2-=u[t]**2 a2%=M a2*=i2 a2%=M ans+=a2*a[s] ans%=M v[s]=0 q.pop() ans-=sum(a) ans%=M print(ans)