結果
問題 |
No.2360 Path to Integer
|
ユーザー |
![]() |
提出日時 | 2025-07-20 04:01:02 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 771 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 82,092 KB |
実行使用メモリ | 561,684 KB |
最終ジャッジ日時 | 2025-07-20 04:01:11 |
合計ジャッジ時間 | 8,944 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | MLE * 1 -- * 1 |
other | -- * 15 |
ソースコード
n=int(input()) a=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 p10=[1] for i in range(sum(len(v) for v in a)): p10+=[p10[-1]*10%M] v=[0]*n u=[0]*n g1=[0]*n q=[0] while len(q)>0: s=q[-1] if v[s]==0: v[s]=1 q+=[t for t in e[s] if v[t]==0] else: for t in e[s]: if v[t]==0: g1[s]+=g1[t]*p10[len(a[s])]+int(a[s])*u[t] g1[s]%=M u[s]+=u[t] g1[s]+=int(a[s]) g1[s]%=M u[s]+=1 v[s]=0 q.pop() g2=g1[:] q=[0] v[s]=1 for s in q: for t in e[s]: if v[t]==0: g3=g2[s] g3-=g1[t]*p10[len(a[s])]+int(a[s])*u[t] g2[t]+=g3*p10[len(a[t])]+int(a[t])*(n-u[t]) g2[t]%=M q+=[t] print(sum(g2)%M)