結果
問題 |
No.1507 Road Blocked
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)