結果
問題 | 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 sysinput = sys.stdin.readlineN=int(input())E=[[] for i in range(N)]for i in range(N-1):x,y=map(int,input().split())x-=1y-=1E[x].append(y)E[y].append(x)mod=998244353ROOT=0QUE=[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]=xQUE.append(to)Children=[1]*(N+1)for x in TOP_SORT[::-1]: #(自分を含む)子ノードの数を調べるChildren[Parent[x]]+=Children[x]ANS=0for 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))%modprint(ANS)