結果
問題 |
No.1507 Road Blocked
|
ユーザー |
![]() |
提出日時 | 2021-05-15 01:10:45 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 876 bytes |
コンパイル時間 | 188 ms |
コンパイル使用メモリ | 82,280 KB |
実行使用メモリ | 473,408 KB |
最終ジャッジ日時 | 2024-10-02 07:59:24 |
合計ジャッジ時間 | 19,980 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 RE * 1 |
ソースコード
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)