Problem p02822 (python)

Fixed submission:
#解説方針#解法1
#https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
from heapq import heappop, heappush
#標準入力
N = int(input())
MOD = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)

#木の探索
parent = [0] * (N + 1)
order = []
stack = [1]
while stack:
    x = stack.pop()
    order.append(x)  # 行きがけ順探索リスト
    for y in L[x]:
        if y == parent[x]:
            continue
        parent[y] = x  # 親ノードを記録
        stack.append(y)
#print(order, parent)

half = pow(2, MOD - 2, MOD)
power_inv = [1] * (N + 1)#2 ** N の逆元の集合
size = [1] * (N + 1)
for i, v in enumerate(order[::-1], 1):#iが1から
    p = parent[v]
    x = size[v]  # vの子孫ノード数（自分も含む）をとる
    size[p] += x  # 親にノード数を加算
    power_inv[i] = power_inv[i - 1] * half % MOD  # [1, 1/2, 1/4, ...]
#print(size)
# 辺iがSに含まれるための必要十分条件による辺の個数の期待値 
# (1 - (1/2) ** i)(1 - (1/2) ** (N - i))を展開して計算
# 根である1の頂点以外は、ある頂点とその親を結ぶ辺を考えた際
# i と N - i個の頂点に別れるので,size[2:]でOK
ans = sum((1 - power_inv[i] - power_inv[N - i] + power_inv[N]) %
          MOD for i in size[2:])  
#ans = sum((1 - (1/2) ** i- (1/2) ** (N - i) + (1/2) ** N) for i in size[2:])  
#print(ans)
ans += 1  # 木の頂点の個数は辺の個数+1
# -「すべての辺が含まれない、つまり空グラフの場合の誤加算」-N/2
ans -= power_inv[N] + N * power_inv[1]  
#ans -= N * power_inv[1]  
ans %= MOD

print(ans)

Buggy submission (verdict: Runtime Error):
#解説方針#解法1
from collections import deque
from heapq import heappop, heappush
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
#P = 10 ** 9 + 7
#N2 = 2 * 100000 + 1
#inv_t = [0]+[1]
#for i in range(2,N2):
#  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = [c]
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = heappop(q)
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        heappush(q, i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
print(y, z)
#ans = inv_t[z] * 1
#print(int(ans))

Buggy submission (verdict: Runtime Error):
#解説方針#解法1
from collections import deque
from heapq import heappop, heappush
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
#P = 10 ** 9 + 7
#N2 = 2 * 100000 + 1
#inv_t = [0]+[1]
#for i in range(2,N2):
#  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = [c]
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = heappop(q)
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        heappush(q, i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
print(y, z)
#ans = inv_t[z] * 1
#print(int(ans))

Buggy submission (verdict: Runtime Error):
#解説方針#解法1
from collections import deque
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
P = 10 ** 9 + 7
N2 = 2 * 100000 + 1
inv_t = [0]+[1]
for i in range(2,N2):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = deque([c])
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = q.pop()
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        q.append(i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
#print(y, z)
ans = inv_t[z] * 1
print(int(ans))

Buggy submission (verdict: Runtime Error):
#解説方針#解法1
from collections import deque
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
P = 10 ** 9 + 7
N2 = 2 * 100000 + 1
inv_t = [0]+[1]
for i in range(2,N2):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = deque([c])
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = q.pop()
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        q.append(i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
#print(y, z)
ans = inv_t[z] * 1
print(int(ans))

Buggy submission (verdict: Runtime Error):
#解説方針#解法1
from collections import deque
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
P = 10 ** 9 + 7
N2 = 2 * 100000 + 1
inv_t = [0]+[1]
for i in range(2,N2):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = deque([c])
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = q.pop()
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        q.append(i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
print(y, z)
ans = inv_t[z] * 1
print(int(ans))

Buggy submission (verdict: Runtime Error):
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
size = [1] * (N + 1)
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(ab, 1, -1)
#print(size)

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = min(size[E[i][0]], size[E[i][1]])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
size = [1] * (N + 1)
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(ab, 1, -1)
print(size)

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = min(size[E[i][0]], size[E[i][1]])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
size = [1] * (N + 1)
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(ab, 1, 0)
print(size)

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = min(size[E[i][0]], size[E[i][1]])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)