結果

問題 No.1507 Road Blocked
ユーザー raven7959raven7959
提出日時 2021-09-24 08:54:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 333 ms / 2,000 ms
コード長 711 bytes
コンパイル時間 136 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 202,324 KB
最終ジャッジ日時 2024-07-05 09:40:24
合計ジャッジ時間 9,885 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
51,840 KB
testcase_01 AC 37 ms
52,608 KB
testcase_02 AC 41 ms
52,480 KB
testcase_03 AC 333 ms
202,324 KB
testcase_04 AC 247 ms
94,452 KB
testcase_05 AC 324 ms
94,468 KB
testcase_06 AC 237 ms
94,460 KB
testcase_07 AC 238 ms
94,720 KB
testcase_08 AC 237 ms
94,336 KB
testcase_09 AC 244 ms
94,208 KB
testcase_10 AC 236 ms
94,364 KB
testcase_11 AC 246 ms
94,344 KB
testcase_12 AC 249 ms
94,504 KB
testcase_13 AC 239 ms
94,156 KB
testcase_14 AC 248 ms
94,416 KB
testcase_15 AC 245 ms
94,464 KB
testcase_16 AC 242 ms
94,336 KB
testcase_17 AC 242 ms
94,208 KB
testcase_18 AC 236 ms
94,304 KB
testcase_19 AC 247 ms
94,360 KB
testcase_20 AC 259 ms
94,360 KB
testcase_21 AC 244 ms
94,208 KB
testcase_22 AC 244 ms
94,772 KB
testcase_23 AC 248 ms
94,380 KB
testcase_24 AC 246 ms
94,152 KB
testcase_25 AC 244 ms
94,424 KB
testcase_26 AC 245 ms
94,280 KB
testcase_27 AC 243 ms
94,304 KB
testcase_28 AC 245 ms
94,680 KB
testcase_29 AC 239 ms
94,208 KB
testcase_30 AC 240 ms
94,592 KB
testcase_31 AC 254 ms
94,364 KB
testcase_32 AC 242 ms
94,700 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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