結果
問題 | No.1507 Road Blocked |
ユーザー | AAAR Salmon |
提出日時 | 2021-05-15 01:10:45 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 876 bytes |
コンパイル時間 | 440 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 474,896 KB |
最終ジャッジ日時 | 2024-04-10 06:20:42 |
合計ジャッジ時間 | 21,027 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
54,684 KB |
testcase_01 | AC | 44 ms
54,548 KB |
testcase_02 | AC | 42 ms
53,816 KB |
testcase_03 | RE | - |
testcase_04 | AC | 684 ms
108,208 KB |
testcase_05 | AC | 672 ms
106,896 KB |
testcase_06 | AC | 673 ms
108,152 KB |
testcase_07 | AC | 734 ms
109,888 KB |
testcase_08 | AC | 658 ms
106,812 KB |
testcase_09 | AC | 642 ms
107,668 KB |
testcase_10 | AC | 408 ms
100,172 KB |
testcase_11 | AC | 586 ms
103,612 KB |
testcase_12 | AC | 425 ms
99,580 KB |
testcase_13 | AC | 608 ms
106,180 KB |
testcase_14 | AC | 614 ms
107,056 KB |
testcase_15 | AC | 722 ms
110,264 KB |
testcase_16 | AC | 704 ms
106,564 KB |
testcase_17 | AC | 518 ms
102,092 KB |
testcase_18 | AC | 384 ms
98,840 KB |
testcase_19 | AC | 597 ms
106,680 KB |
testcase_20 | AC | 585 ms
104,672 KB |
testcase_21 | AC | 631 ms
106,092 KB |
testcase_22 | AC | 382 ms
100,868 KB |
testcase_23 | AC | 528 ms
102,860 KB |
testcase_24 | AC | 374 ms
98,056 KB |
testcase_25 | AC | 705 ms
107,020 KB |
testcase_26 | AC | 380 ms
98,564 KB |
testcase_27 | AC | 602 ms
105,556 KB |
testcase_28 | AC | 632 ms
106,984 KB |
testcase_29 | AC | 782 ms
109,112 KB |
testcase_30 | AC | 390 ms
99,384 KB |
testcase_31 | AC | 334 ms
99,380 KB |
testcase_32 | AC | 598 ms
105,844 KB |
ソースコード
from collections import deque from sys import stderr, setrecursionlimit setrecursionlimit(200000) MOD = 998244353 N = int(input()) edges = [[] for _ in range(N + 1)] for _ in range(N - 1): u, v = map(int, input().split()) edges[u].append(v) edges[v].append(u) parent = [-1] * (N + 1) parent[1] = 0 children = [[] for _ in range(N + 1)] q = deque([1]) while q: p = q.popleft() for n in edges[p]: if parent[n] != -1: continue parent[n] = p children[p].append(n) q.append(n) descendant = [0] * (N + 1) def bfs(n): if not children[n]: descendant[n] = 1 return 1 descendant[n] = sum(bfs(c) for c in children[n]) + 1 return descendant[n] bfs(1) # print(descendant, file=stderr) # ans = a / b a = N * (N - 1)**2 // 2 b = N * (N - 1)**2 // 2 for n in range(2, N + 1): a -= descendant[n] * (N - descendant[n]) print(a * pow(b, MOD - 2, MOD) % MOD)