結果
問題 | No.1507 Road Blocked |
ユーザー | wolgnik |
提出日時 | 2021-05-14 22:26:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 718 bytes |
コンパイル時間 | 412 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 96,968 KB |
最終ジャッジ日時 | 2024-04-10 00:56:59 |
合計ジャッジ時間 | 6,876 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
52,740 KB |
testcase_01 | AC | 33 ms
52,632 KB |
testcase_02 | AC | 33 ms
52,692 KB |
testcase_03 | AC | 97 ms
94,152 KB |
testcase_04 | AC | 163 ms
95,392 KB |
testcase_05 | AC | 161 ms
95,372 KB |
testcase_06 | AC | 157 ms
95,840 KB |
testcase_07 | AC | 160 ms
95,708 KB |
testcase_08 | AC | 160 ms
95,908 KB |
testcase_09 | AC | 161 ms
96,688 KB |
testcase_10 | AC | 163 ms
96,852 KB |
testcase_11 | AC | 167 ms
96,968 KB |
testcase_12 | AC | 156 ms
96,752 KB |
testcase_13 | AC | 162 ms
96,592 KB |
testcase_14 | AC | 156 ms
95,904 KB |
testcase_15 | AC | 163 ms
96,376 KB |
testcase_16 | AC | 161 ms
96,600 KB |
testcase_17 | AC | 161 ms
96,540 KB |
testcase_18 | AC | 169 ms
96,824 KB |
testcase_19 | AC | 163 ms
95,576 KB |
testcase_20 | AC | 164 ms
96,744 KB |
testcase_21 | AC | 165 ms
96,932 KB |
testcase_22 | AC | 167 ms
96,680 KB |
testcase_23 | AC | 156 ms
95,840 KB |
testcase_24 | AC | 150 ms
96,100 KB |
testcase_25 | AC | 155 ms
95,824 KB |
testcase_26 | AC | 164 ms
95,392 KB |
testcase_27 | AC | 160 ms
94,596 KB |
testcase_28 | AC | 159 ms
95,892 KB |
testcase_29 | AC | 162 ms
96,604 KB |
testcase_30 | AC | 157 ms
95,884 KB |
testcase_31 | AC | 164 ms
96,616 KB |
testcase_32 | AC | 160 ms
95,900 KB |
ソースコード
import sys input = sys.stdin.readline N = int(input()) e = [[] for _ in range(N + 1)] for _ in range(N - 1): u, v = map(int, input().split()) e[u].append(v) e[v].append(u) mod = 998244353 s = [1] vis = [0] * (N + 1) parent = [0] * (N + 1) vis[1] = 1 order = [] while len(s): x = s.pop() order.append(x) for y in e[x]: if vis[y]: continue parent[y] = x vis[y] = 1 s.append(y) size = [1] * (N + 1) order.reverse() for y in order[: -1]: x = parent[y] size[x] += size[y] res = 0 for y in range(2, N + 1): x = parent[y] u = N - size[y] d = size[y] res += u * d res %= mod #print(y, u, d) res *= pow(N * (N - 1) * (N - 1) // 2, mod - 2, mod) res %= mod print((1 - res) % mod)