Problem p02794 (python)

Fixed submission:
# ABC152F

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





from collections import defaultdict
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-len(s)) * (-1)**(sum(ind)+1)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], set(), 0)
print(2**(n-1) - ans)

Buggy submission (verdict: Runtime Error):
# ABC152F

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




from collections import defaultdict
from queue import deque
import itertools
import functools
import numpy as np
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = np.zeros(n-1, dtype=bool)
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es[uv2e[u,seen[u]]] = True
        if seen[u]==start:
            break
        u = seen[u]
    return es

n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1, u-1] = i
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-s.sum()) * (-1)**((sum(ind)+1)%2)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], np.zeros(n-1, dtype=bool), 0)
print(2**(n-1) - ans)