結果

問題 No.1507 Road Blocked
ユーザー raven7959
提出日時 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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0