結果

問題 No.1507 Road Blocked
ユーザー titia
提出日時 2021-05-15 03:08:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 498 ms / 2,000 ms
コード長 819 bytes
コンパイル時間 93 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 33,536 KB
最終ジャッジ日時 2024-10-02 09:55:54
合計ジャッジ時間 15,706 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
N=int(input())
E=[[] for i in range(N)]
for i in range(N-1):
x,y=map(int,input().split())
x-=1
y-=1
E[x].append(y)
E[y].append(x)
mod=998244353
ROOT=0
QUE=[ROOT]
Parent=[-1]*(N+1)
Parent[ROOT]=N # ROOT.
TOP_SORT=[] #
while QUE: #
x=QUE.pop()
TOP_SORT.append(x)
for to in E[x]:
if Parent[to]==-1:
Parent[to]=x
QUE.append(to)
Children=[1]*(N+1)
for x in TOP_SORT[::-1]: #調
Children[Parent[x]]+=Children[x]
ANS=0
for i in range(1,N):
ANS+=Children[i]*(N-Children[i])
ANS=(1-ANS*pow(N-1,mod-2,mod)*pow(N*(N-1)//2,mod-2,mod))%mod
print(ANS)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0