結果

問題 No.2214 Products on Tree
ユーザー sasa8uyauya
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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])
0