Problem p02793 (python)

Fixed submission:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    def factorize(n):
        ret = {}
        d = 2
        mx = int(n ** 0.5) + 1
        while d < mx:
            if n % d == 0:
                ret[d] = 0
            while n % d == 0:
                ret[d] += 1
                n //= d
            d += 1
        if n > 1:
            if n not in ret:
                ret[n] = 1
            else:
                ret[n] += 1
        return ret
    divs = {}
    cur = 1
    ret = 0
    for val in A:
        facs = factorize(val)
        tmp = 1
        for k, cnt in facs.items():
            if not k in divs:
                divs[k] = 0
            if divs[k] < cnt:
                tmp *= k ** (cnt - divs[k])
                divs[k] = cnt
        cur *= tmp
        ret *= tmp
        ret += cur // val
        ret %= MOD
        #print(tmp, cur)
        #print(divs)
        #print(ret)
        #print('-------')
    print(ret)
    return ret

def solve_(N: int, A: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = A[0]
    for v in A:
        tmp = gcd(g, v)
        g = g * v // tmp
    ret = 0
    for v in A:
        ret += g // v
        ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]", M: int, u: "List[int]", v: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[a[i] - 1].append((b[i] - 1, i))
        conns[b[i] - 1].append((a[i] - 1, i))
    bits = []
    def dfs(idx, t, visited):
        visited[idx] = True
        if idx == t:
            return 0
        for node, edge_idx in conns[idx]:
            if not visited[node]:
                tmp = dfs(node, t, visited)
                if tmp is not None:
                    return tmp + (1 << edge_idx)
        return None
    for j in range(M):
        visited = [False] * N
        bit = dfs(u[j] - 1, v[j] - 1, visited)
        bits.append(bit)

    ret = 0
    for i in range(2 ** (N - 1)):
        for j in range(M):
            if i & bits[j] == 0:
                break
        else:
            ret += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, b, M, u, v)

if __name__ == '__main__':
    main()