結果
問題 | No.1124 Earthquake Safety |
ユーザー |
![]() |
提出日時 | 2020-07-22 22:46:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 2,300 ms / 3,000 ms |
コード長 | 1,349 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 112,156 KB |
最終ジャッジ日時 | 2024-06-22 23:46:11 |
合計ジャッジ時間 | 82,761 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 58 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines MOD = 10**9 + 7 inv2 = pow(2, MOD - 2, MOD) inv4 = inv2**2 % MOD def dfs_order(G, root=1): parent = [0] * (N + 1) order = [] stack = [root] while stack: x = stack.pop() order.append(x) for y in G[x]: if y == parent[x]: continue parent[y] = x stack.append(y) return parent, order N = int(readline()) m = map(int, read().split()) G = [[] for _ in range(N + 1)] for a, b in zip(m, m): G[a].append(b) G[b].append(a) root = 1 parent, order = dfs_order(G, root) mu1 = [0] * (N + 1) var1 = [0] * (N + 1) for v in order[::-1]: p = parent[v] mu1[v] += 1 mu1[v] %= MOD var1[v] %= MOD mu1[p] += inv2 * mu1[v] var1[p] += var1[v] * inv2 + mu1[v] * mu1[v] * inv4 mu2 = [0] * (N + 1) var2 = [0] * (N + 1) for v in order: mu2[v] = mu1[v] var2[v] = var1[v] if v == root: continue p = parent[v] mu = mu2[p] - mu1[v] * inv2 var = var2[p] - inv2 * var2[v] - mu1[v]**2 * inv4 mu2[v] += mu * inv2 var2[v] += mu * mu * inv4 + var * inv2 mu2[v] %= MOD var2[v] %= MOD ans = 0 for v in range(1, N+1): ans += mu2[v] ** 2 + var2[v] ans *= pow(2, N-1, MOD) print(ans % MOD)