結果
問題 | No.1507 Road Blocked |
ユーザー |
👑 |
提出日時 | 2022-01-27 00:37:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 287 ms / 2,000 ms |
コード長 | 569 bytes |
コンパイル時間 | 422 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 177,152 KB |
最終ジャッジ日時 | 2024-12-23 22:23:33 |
合計ジャッジ時間 | 10,906 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import syssys.setrecursionlimit(10 ** 9)MOD = 998244353n = int(input())edges = [[] for _ in range(n)]for _ in range(n - 1):a, b = map(int, input().split())a -= 1b -= 1edges[a].append(b)edges[b].append(a)ans = 0def dfs(pos, bpos):global ansret = 1for npos in edges[pos]:if npos == bpos:continueret += dfs(npos, pos)if pos != 0:ans += n * (n - 1) // 2 - ret * (n - ret)return retdfs(0, -1)div = n * (n - 1) // 2 * (n - 1)print(ans * pow(div, MOD - 2, MOD) % MOD)