結果
問題 | No.2214 Products on Tree |
ユーザー |
![]() |
提出日時 | 2025-02-01 13:44:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 661 ms / 3,000 ms |
コード長 | 543 bytes |
コンパイル時間 | 785 ms |
コンパイル使用メモリ | 82,104 KB |
実行使用メモリ | 133,516 KB |
最終ジャッジ日時 | 2025-02-01 13:44:46 |
合計ジャッジ時間 | 17,367 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
n=int(input()) e=[[] for i in range(n)] for i in range(n-1): a,b=map(int,input().split()) a-=1 b-=1 e[a]+=[b] e[b]+=[a] M=998244353 v=[0]*n p=[[1,0] for i in range(n)] 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: q+=[t] else: for t in e[s]: if v[t]==0: p[s][1]=p[s][1]*(p[t][0]+p[t][1])+p[s][0]*p[t][1] p[s][1]%=M p[s][0]=p[s][0]*(p[t][0]+p[t][1]) p[s][0]%=M p[s][1]+=p[s][0] p[s][1]%=M v[s]=0 q.pop() print(p[0][1])