Problem p02822 (python)

Fixed submission:
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())
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)

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:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 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)

Buggy submission (verdict: Runtime Error):
from sys import stdin, setrecursionlimit
from math import gcd

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
prev = [-1] * N


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


dfs1(0)

numer = 0
seen = [False] * N

pow2 = pow(2, N - 1, MOD)


def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    if prev[v] != -1:
        nodes.append(N - childs[v] - 1)
    for nv in G[v]:
        if not seen[nv]:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = pow2 - (sum(pow(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)
denom = pow(2, N, MOD)
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Buggy submission (verdict: Runtime Error):
from sys import stdin, setrecursionlimit
from math import gcd

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
prev = [-1] * N


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


dfs1(0)

numer = 0
seen = [False] * N

pow2 = pow(2, N - 1, MOD)


def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    if prev[v] != -1:
        nodes.append(N - childs[v] - 1)
    for nv in G[v]:
        if not seen[nv]:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = pow2 - (sum(pow(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)
denom = pow(2, N, MOD)
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)