結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2021-05-14 22:24:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 570 ms / 2,000 ms |
コード長 | 902 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 102,312 KB |
最終ジャッジ日時 | 2024-10-02 02:01:34 |
合計ジャッジ時間 | 17,236 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
N = int(input())adj = [[] for i in range(N)]E = []for i in range(N - 1):u, v = map(int, input().split())u -= 1v -= 1adj[u].append(v)adj[v].append(u)E.append((u, v))depth = [-1] * Nfrom collections import dequedepth[0] = 0qu = deque([0])while len(qu):v = qu.popleft()for nv in adj[v]:if depth[nv] == -1:depth[nv] = depth[v] + 1qu.append(nv)V = [i for i in range(N)]V.sort(key = lambda x: depth[x], reverse = True)dp = [1] * Nfor v in V:for nv in adj[v]:if depth[nv] > depth[v]:dp[v] += dp[nv]ans = 0MOD = 998244353for e in E:u, v = eif depth[u] > depth[v]:u, v = v, ua = dp[v]b = N - dp[v]tmp = a * (a - 1) + b * (b - 1)tmp = tmp * pow(N * (N - 1), MOD - 2, MOD)ans = (ans + tmp) % MODans = ans * pow(N - 1, MOD - 2, MOD)print(ans % MOD)