結果
問題 |
No.2360 Path to Integer
|
ユーザー |
![]() |
提出日時 | 2025-07-19 18:00:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 525 ms / 2,500 ms |
コード長 | 848 bytes |
コンパイル時間 | 482 ms |
コンパイル使用メモリ | 82,600 KB |
実行使用メモリ | 169,736 KB |
最終ジャッジ日時 | 2025-07-19 18:00:20 |
合計ジャッジ時間 | 6,386 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 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] while len(q)>0: s=q[-1] if v[s]==0: v[s]=1 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] else: v[s]=0 q.pop() print(sum(g2)%M)