結果

問題 No.1507 Road Blocked
ユーザー AAAR Salmon
提出日時 2021-05-15 01:03:53
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 830 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 110,100 KB
最終ジャッジ日時 2024-10-02 07:52:31
合計ジャッジ時間 18,312 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import deque
from sys import stderr
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0