#1059457 (PyPy3) No.1507 Road Blocked

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX