結果

問題 No.2504 NOT Path Painting
ユーザー sasa8uyauya
提出日時 2025-02-08 15:00:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 922 ms / 2,000 ms
コード長 831 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,616 KB
実行使用メモリ 110,284 KB
最終ジャッジ日時 2025-02-08 15:01:15
合計ジャッジ時間 17,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

M=998244353
T=int(input())
for _ in range(T):
  n=int(input())
  i2=pow(2,M-2,M)
  ic=pow(n*(n+1)*i2,M-2,M)
  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]
  p1=0
  p2=0
  v=[0]*n
  u=[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:
      u[s]=1+sum(u[t] for t in e[s] if v[t]==0)
      c1=0
      c2=0
      for t in e[s]:
        if v[t]==0:
          c1+=u[t]
          c2+=u[t]**2
        else:
          c1+=n-u[s]
          c2+=(n-u[s])**2
        c1%=M
        c2%=M
      g1=(c1**2-c2)*i2+n
      p1+=pow(1-g1*ic%M,M-2,M)
      for t in e[s]:
        if v[t]==0:
          g2=u[t]*(n-u[t])
          p2+=pow(1-g2*ic%M,M-2,M)
      v[s]=0
      q.pop()
  print((p1-p2)%M)
0