結果
問題 |
No.2360 Path to Integer
|
ユーザー |
![]() |
提出日時 | 2025-07-20 04:01:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 594 ms / 2,500 ms |
コード長 | 784 bytes |
コンパイル時間 | 426 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 170,256 KB |
最終ジャッジ日時 | 2025-07-20 04:01:39 |
合計ジャッジ時間 | 5,888 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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] 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] v[t]=1 print(sum(g2)%M)