結果

問題 No.1507 Road Blocked
コンテスト
ユーザー raven7959
提出日時 2021-09-24 08:54:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 333 ms / 2,000 ms
コード長 711 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 136 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 202,324 KB
最終ジャッジ日時 2024-07-05 09:40:24
合計ジャッジ時間 9,885 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(10**9)
N=int(input())
E=[]
G=[[] for _ in range(N)]
for _ in range(N-1):
  u,v=map(lambda x:int(x)-1,input().split())
  E.append((u,v))
  G[u].append(v)
  G[v].append(u)
subtree_size=[1]*N
def dfs(G,v,p=-1):
  for nextv in G[v]:
    if nextv!=p:
      dfs(G,nextv,v)
  for c in G[v]:
    if c!=p:
      subtree_size[v]+=subtree_size[c]
dfs(G,0)
p=0
for u,v in E:
  n=min(subtree_size[u],subtree_size[v])
  # print(u,v,n)
  p+=n*(n-1)//2+(N-n)*(N-n-1)//2
q=N*(N-1)//2*(N-1)
while q%998244353==0:
  p//=998244353
  q//=998244353
# print(p,q)
def extgcd(a,b):
  if b:
    d,y,x=extgcd(b,a%b)
    y-=(a//b)*x
    return d,x,y
  return a,1,0
print(p*extgcd(q,998244353)[1]%998244353)
0