結果
問題 | No.2949 Product on Tree |
ユーザー |
![]() |
提出日時 | 2024-10-25 21:59:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,215 ms / 2,000 ms |
コード長 | 902 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 142,156 KB |
最終ジャッジ日時 | 2024-10-25 22:00:49 |
合計ジャッジ時間 | 49,500 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
N=int(input()) A=list(map(int,input().split())) G=[[] for i in range(N)] for i in range(N-1): a,b=map(int,input().split()) G[a-1].append(b-1) G[b-1].append(a-1) dist=[-1]*N dist[0]=0 from collections import deque S=deque() S.append(0) while S: x=S.pop() for y in G[x]: if dist[y]>=0: continue dist[y]=dist[x]+1 S.append(y) L=[] for i in range(N): L.append((dist[i],i)) mod=998244353 dp=[0]*N result=0 L.sort(reverse=True) k=pow(2,-1,mod) for i in range(N): x=L[i][1] count=0 p=A[x] for y in G[x]: if dist[y]<dist[x]: continue result+=dp[y]*p result%=mod dp[x]+=dp[y]*p dp[x]%=mod count+=dp[y] count%=mod score=0 for y in G[x]: if dist[y]<dist[x]: continue w=(count-dp[y])*dp[y] w%=mod w*=A[x] w%=mod score+=w score%=mod result+=score*k result%=mod dp[x]+=A[x] dp[x]%=mod print(result)