結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2023-02-06 12:33:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 95,488 KB |
最終ジャッジ日時 | 2024-07-04 17:33:14 |
合計ジャッジ時間 | 10,002 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
mod = 998244353 def non_rec_dfs(s): stack = [] stack.append(~s) stack.append(s) par = [-1] * N sz = [1] * N ans = 0 while stack: u = stack.pop() if u >= 0: stack.append(~u) for v in G[u]: if v == par[u]: continue par[v] = u stack.append(v) else: u = ~u if par[u] != -1: sz[par[u]] += sz[u] ans += sz[u] * (sz[u] - 1)//2 ans += (N - sz[u]) * (N - sz[u] - 1)//2 ans %= mod return ans N = int(input()) G = [[] for i in range(N)] for i in range(N - 1): A, B = map(int, input().split()) A, B = A - 1, B - 1 G[A].append(B) G[B].append(A) ans = non_rec_dfs(0) all = N * (N - 1)//2 * (N - 1) ans *= pow(all, mod - 2, mod) ans %= mod print(ans)