結果
問題 | 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 = 998244353def non_rec_dfs(s):stack = []stack.append(~s)stack.append(s)par = [-1] * Nsz = [1] * Nans = 0while stack:u = stack.pop()if u >= 0:stack.append(~u)for v in G[u]:if v == par[u]:continuepar[v] = ustack.append(v)else:u = ~uif par[u] != -1:sz[par[u]] += sz[u]ans += sz[u] * (sz[u] - 1)//2ans += (N - sz[u]) * (N - sz[u] - 1)//2ans %= modreturn ansN = 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 - 1G[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 %= modprint(ans)