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):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)





children_counts = [None for _ in range(N)]
parents = [None] * N


def dfs(v, parent=None):
    parents[v] = parent
    counts = {}
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        cnt = dfs(u, v)
        if cnt in counts:
            counts[cnt] += 1
        else:
            counts[cnt] = 1
        ret += cnt
    ret += 1
    if v != root:
        if N - ret in counts:
            counts[N - ret] += 1
        else:
            counts[N - ret] = 1
    children_counts[v] = counts
    return ret


root = 0
dfs(root)

exit()
pow2 = [1]
p = 1
for _ in range(N):
    p = (p * 2) % MOD
    pow2.append(p)


E = [0] * N
for v, counts in enumerate(children_counts):
    if len(graph[v]) == 1:
        
        E[v] = pow2[N]
        continue
    
    e = pow2[N - 1]
    
    for children, cnt in counts.items():
        
        
        curo = pow2[children] - 1
        e += (curo * cnt) % MOD
    
    
    E[v] = (e + 1) % MOD

E = [(pow2[N] - e) % MOD for e in E]
ans = div_mod(sum(E), pow2[N], MOD)
print(ans)


import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
#
# N = 5

# AB = [(a + 1, b + 1) for a, b in AB]
# print(N)
# for a, b in AB:
#     print(a, b)






graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)



root = 0
stack = [(0, None)]
hist = []
while stack:
    v, parent = stack.pop()
    hist.append((v, parent))
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

subtree_sizes = [0] * N
hist.reverse()
for v, parent in hist:
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        ret += subtree_sizes[u]
    subtree_sizes[v] = ret + 1

pow2 = [1]
p = 1
for _ in range(N + 10):
    p = p * 2 % MOD
    pow2.append(p)



e_exp = 0
for v in range(N):
    for u in graph[v]:
        if v < u:
            continue
        
        s = min(subtree_sizes[v], subtree_sizes[u])
        t = N - s

        
        cnt = pow2[N]
        
        cnt -= pow2[t]
        
        cnt -= pow2[s]
        
        cnt += 1
        e_exp += cnt
        e_exp %= MOD


v_exp = e_exp + pow2[N] - 1
ans = div_mod(v_exp, pow2[N], MOD) - div_mod(N, 2, MOD)
ans %= MOD
print(ans)
# print((v_exp / (2 ** N)) - N / 2)


Verdicts: Wrong Answer

Accepted