Problem p02822 (python)

Fixed submission:
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))
    write = lambda x: sys.stdout.write(x+"\n")


    ### 木の読み込み tree

    # サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
    from collections import defaultdict
    # import numpy as np
    # from numba import njit
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        u -= 1
        v -= 1
        ns[u].add(v)
        ns[v].add(u)


    # 再帰を用いないver.
    def dfs(start):
        q = [start]
        # 行きがけ順
        seen = [None]*n
        # 帰りがけ順
        done = [None]*n
        parent = [None]*n
        parent[start] = -1
        d0 = 0
        d1 = n
        while q:
            u = q.pop()
            if u>=0:
                if seen[u] is not None:
                    continue
                seen[u] = d0
                d0 += 1
                q.append(~u)
                for v in ns[u]:
                    if seen[v] is None:
                        q.append(v)
                        parent[v] = u
            else:
                d1 -= 1
                done[~u] = d1
        return seen, done, parent
    seen, done, parent = dfs(0)
    done = [(u,d) for u,d in enumerate(done)]
    done.sort(key = lambda x: -x[1])
    bs = {}
    for u,_ in done:
        p = parent[u]
        bs[p,u] = 1 + sum(bs[u,v] for v in ns[u] if v!=p)

    bs[0,-1] = 0
    for u,_ in reversed(done):
        p = parent[u]
        for v in ns[u]:
            if v==p:
                continue
            bs[v,u] = bs[p,u] - bs[u,v] + bs[u,p]

    M = 10**9 + 7
    p1 = pow(2, n-1, M)
    p2 = pow(2, n, M)
    p3 = pow(p2, M-2, M)
    ans = 0
    for u in range(n):
        s = 0
        for v in ns[u]:
            s += pow(2, bs[u,v], M) - 1
            s %= M
        val = p1 - s - 1
        ans += val
        ans %= M
    ans *= p3
    ans %= M
    print(ans%M)
# from line_profiler import LineProfiler
# lp = LineProfiler()
# lp.add_function(main)
# lp.runcall(main)
# lp.print_stats()
main()

Buggy submission (verdict: Runtime Error):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 木の読み込み tree

# サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

bs = {}
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b += bb
    bs[p,u] = b
    return b

def sub2(u, p):
    for v in ns[u]:
        if v==p:
            continue
        b1 = bs[p,u]
        b2 = bs[u,v]
        b3 = bs[u,p]
        # 逆向き枝の計算
        bb = b1 - b2 + b3
        bs[v,u] = bb
        sub2(v,u)
        
sub(0, -1)
bs[0,-1] = 0
sub2(0,-1)
# ans[0] = bs[-1,0]
raise RuntimeError
M = 10**9 + 7
p1 = pow(2, n-1, M)
p2 = pow(2, n, M)
p3 = pow(p2, M-2, M)
ans = 0
for u in range(n):
    s = 0
    for v in ns[u]:
        s += pow(2, bs[u,v], M) - 1
        s %= M
    val = p1 - s - 1
    ans += val
    ans %= M
ans *= p3
ans %= M
print(ans%M)