結果

問題 No.1507 Road Blocked
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:49:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 1,208 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 152 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 96,720 KB
最終ジャッジ日時 2025-03-20 20:49:34
合計ジャッジ時間 6,707 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(1 << 25)

mod = 998244353

n = int(sys.stdin.readline())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, sys.stdin.readline().split())
    adj[u].append(v)
    adj[v].append(u)

sum_contrib = 0
stack = [(1, -1, False)]
size = [0] * (n + 1)  # size[0] unused

while stack:
    u, parent, visited = stack.pop()
    if not visited:
        stack.append((u, parent, True))
        for v in adj[u]:
            if v != parent:
                stack.append((v, u, False))
        size[u] = 1
    else:
        for v in adj[u]:
            if v != parent:
                s = size[v]
                contrib = (s * (s - 1) // 2) + ((n - s) * (n - s - 1) // 2)
                sum_contrib += contrib
                size[u] += s

# Calculate denominator modulo mod
inv2 = pow(2, mod - 2, mod)
denominator_mod = (n % mod) * ((n - 1) % mod) % mod
denominator_mod = denominator_mod * ((n - 1) % mod) % mod
denominator_mod = denominator_mod * inv2 % mod

sum_contrib_mod = sum_contrib % mod

if denominator_mod == 0:
    print(0)
else:
    inv_denominator = pow(denominator_mod, mod - 2, mod)
    ans = (sum_contrib_mod * inv_denominator) % mod
    print(ans)
0