結果
問題 | No.1507 Road Blocked |
ユーザー | GER_chen |
提出日時 | 2021-05-14 22:44:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 640 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 112,640 KB |
最終ジャッジ日時 | 2024-04-10 01:48:27 |
合計ジャッジ時間 | 11,727 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
53,420 KB |
testcase_01 | AC | 35 ms
53,312 KB |
testcase_02 | AC | 38 ms
52,320 KB |
testcase_03 | AC | 190 ms
109,672 KB |
testcase_04 | AC | 340 ms
112,180 KB |
testcase_05 | AC | 334 ms
112,304 KB |
testcase_06 | AC | 335 ms
111,988 KB |
testcase_07 | AC | 330 ms
112,320 KB |
testcase_08 | AC | 334 ms
112,152 KB |
testcase_09 | AC | 318 ms
112,640 KB |
testcase_10 | AC | 338 ms
112,220 KB |
testcase_11 | AC | 335 ms
112,268 KB |
testcase_12 | AC | 333 ms
112,544 KB |
testcase_13 | AC | 343 ms
112,256 KB |
testcase_14 | AC | 329 ms
111,896 KB |
testcase_15 | AC | 341 ms
112,384 KB |
testcase_16 | AC | 337 ms
112,408 KB |
testcase_17 | AC | 332 ms
112,580 KB |
testcase_18 | AC | 336 ms
112,292 KB |
testcase_19 | AC | 339 ms
112,244 KB |
testcase_20 | AC | 332 ms
112,324 KB |
testcase_21 | AC | 326 ms
112,336 KB |
testcase_22 | AC | 339 ms
112,324 KB |
testcase_23 | AC | 328 ms
111,884 KB |
testcase_24 | AC | 347 ms
112,168 KB |
testcase_25 | AC | 336 ms
111,968 KB |
testcase_26 | AC | 334 ms
112,024 KB |
testcase_27 | AC | 339 ms
112,000 KB |
testcase_28 | AC | 338 ms
111,944 KB |
testcase_29 | AC | 335 ms
112,016 KB |
testcase_30 | AC | 342 ms
112,180 KB |
testcase_31 | AC | 340 ms
112,172 KB |
testcase_32 | AC | 328 ms
112,116 KB |
ソースコード
mod = 998244353 n = int(input()) Adj = [set() for _ in range(n)] for _ in range(n-1): u, v = map(int, input().split()) Adj[u-1].add(v-1) Adj[v-1].add(u-1) Parent = [-1]*n Size = [0]*n D = [0] Sort = [] while D: v = D.pop() Sort.append(v) for nxt in Adj[v]: if nxt != Parent[v]: Parent[nxt] = v D.append(nxt) for i in Sort[::-1]: Size[i] += 1 for child in Adj[i]: if child != Parent[i]: Size[i] += Size[child] ans = 0 cff = pow((n*(n-1)**2)//2, mod-2, mod) for i in range(1, n): s = Size[i] ans += s*(n-s) ans %= mod print((mod+1-ans*cff)%mod)