Problem: Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).  Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)  Let the _holeyness_ of S be the number of white vertices contained in S. Find the expected holeyness of S.  Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.

Submission attempts (in order):

from collections import deque

N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] 
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]


def dfs(c, d):
  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      



x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N

  
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
    

y, z = y % mod, int(z % mod)
y = y % z
print(y, z)
ans = inv_t[z] * 1
print(int(ans))




from collections import deque
from heapq import heappop, heappush

N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] 
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]

#  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]


def dfs(c, d):
  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      



x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N

  
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
    

y, z = y % mod, int(z % mod)
y = y % z
print(y, z)

#print(int(ans))




#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)] 
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)
size = [1] * (N + 1)
for i, v in enumerate(order[::-1], 1):
    p = parent[v]
    x = size[v]  
    size[p] += x  
    power_inv[i] = power_inv[i - 1] * half % MOD  # [1, 1/2, 1/4, ...]
#print(size)




ans = sum((1 - power_inv[i] - power_inv[N - i] + power_inv[N]) %
          MOD for i in size[2:])  

#print(ans)
ans += 1  

ans -= power_inv[N] + N * power_inv[1]  
#ans -= N * power_inv[1]  
ans %= MOD

print(ans)

Verdicts: Runtime Error

Runtime Error

Accepted