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 sys import stdin, setrecursionlimit
from functools import lru_cache

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

childs = [0] * N
seen = [False] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

@lru_cache(maxsize=None)
def power(x, y, z):
    return pow(x, y, z)


#     global numer

#     nodes = []
#     for nv in G[v]:

#             nodes.append(N - childs[v] - 1)
#         else:
#             nodes.append(childs[nv] + 1)
#     if len(nodes) > 1:
#         this_numer = power(2, N - 1, MOD) - (sum(power(2, n, MOD) - 1 for n in nodes) + 1)
#         numer = (numer + this_numer) % MOD
#     for nv in G[v]:
#         if not seen[nv]:
#             dfs2(nv)
#     return


# dfs2(0)

# ans = numer * pow(denom, MOD - 2, MOD) % MOD
# print(ans)


from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
m = map(int, stdin.buffer.read().split())
AB = zip(m, m)
G = [[] for _ in range(N)]
for a, b in AB:
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)


import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

    pow2 = [0] * (N + 1)
    pow2[0] = 1
    for i in range(N):
        pow2[i + 1] = pow2[i] * 2 % MOD

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - pow2[N - nodes[v]]) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - pow2[nodes[nv]] + 1) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted