結果

問題 No.2504 NOT Path Painting
コンテスト
ユーザー sasa8uyauya
提出日時 2025-02-08 14:57:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 878 bytes
コンパイル時間 1,098 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 220,100 KB
最終ジャッジ日時 2025-02-08 14:58:03
合計ジャッジ時間 51,100 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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