結果

問題 No.1507 Road Blocked
ユーザー lam6er
提出日時 2025-03-26 15:45:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 285 ms / 2,000 ms
コード長 1,993 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 101,120 KB
最終ジャッジ日時 2025-03-26 15:45:50
合計ジャッジ時間 9,807 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)
MOD = 998244353

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

    # Compute parents and sizes using DFS post-order traversal
    parents = [0] * (n + 1)
    sizes = [1] * (n + 1)
    visited = [False] * (n + 1)
    stack = [(1, False)]
    parents[1] = -1  # Root has no parent

    while stack:
        node, processed = stack.pop()
        if processed:
            for neighbor in edges[node]:
                if parents[neighbor] == node:
                    sizes[node] += sizes[neighbor]
            continue
        if visited[node]:
            continue
        visited[node] = True
        stack.append((node, True))
        for neighbor in edges[node]:
            if not visited[neighbor] and neighbor != parents[node]:
                parents[neighbor] = node
                stack.append((neighbor, False))

    sum_num_numerator = 0
    for u, v in stored_edges:
        if parents[v] == u:
            s = sizes[v]
        elif parents[u] == v:
            s = sizes[u]
        else:
            assert False, "Edge not in parent-child relationship"
        term = s * (s - 1) + (n - s) * (n - s - 1)
        sum_num_numerator += term

    sum_num = sum_num_numerator // 2

    # Compute denominator mod MOD: (n*(n-1)^2) / 2
    if n == 0 or n == 1:
        den_mod = 0
    else:
        n_mod = n % MOD
        n_minus_1_mod = (n - 1) % MOD
        inv2 = (MOD + 1) // 2  # Modular inverse of 2
        denominator = (n_mod * pow(n_minus_1_mod, 2, MOD)) % MOD
        denominator = (denominator * inv2) % MOD
        inv_den = pow(denominator, MOD - 2, MOD) if denominator != 0 else 0

    result = (sum_num % MOD) * inv_den % MOD
    print(result)

if __name__ == "__main__":
    main()
0