結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2025-01-03 00:03:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 1,470 bytes |
コンパイル時間 | 461 ms |
コンパイル使用メモリ | 82,280 KB |
実行使用メモリ | 90,908 KB |
最終ジャッジ日時 | 2025-01-03 00:03:22 |
合計ジャッジ時間 | 11,833 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
## https://yukicoder.me/problems/no/1507from collections import dequeMOD = 998244353def main():N = int(input())next_nodes = [[] for _ in range(N)]for _ in range(N - 1):u, v = map(int, input().split())next_nodes[u - 1].append(v - 1)next_nodes[v - 1].append(u - 1)answer = 0child_num = [0] * Nparents = [-2] * Nstack = deque()stack.append((0, 0))parents[0] = -1inv2 = pow(2, MOD - 2, MOD)pp = (N * (N - 1)) % MODpp *= inv2pp %= MODpp = pow(pp, MOD - 2, MOD)p_n = pow(N - 1, MOD - 2, MOD)while len(stack) > 0:v, index = stack.pop()while index < len(next_nodes[v]):w = next_nodes[v][index]if w == parents[v]:index += 1continueparents[w] = vstack.append((v, index + 1))stack.append((w, 0))breakif index == len(next_nodes[v]):c = 1 + child_num[v]d = N - cp = (c * (c - 1)) % MODp += (d * (d - 1)) % MODp *= inv2p %= MODp *= ppp %= MODif parents[v] != -1:answer += (p * p_n) % MODanswer %= MODchild_num[parents[v]] += 1 + child_num[v]print(answer)if __name__ == "__main__":main()