Problem: We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i.   Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?    * The i-th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i, which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.

Submission attempts (in order):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 +7

n = int(readline)
ab = list(list(map(int,readline().split()))for _ in range(n-1))
m=int(readline())
uv=list(list(map(int,readline().split()))for _ in range(m))

graph = [[]for _ in range(n+1)]
for i ,(a,b) in enumerate(ab):
    graph[a].append((b,i))
    graph[b].append((a,i))

def get_path(u,v):
    INF = 100
    visited =[False]*(n+1)
    pred =[None]*(n+1)
    stack =[u]
    visited[u]=True
    while stack:
        v = stack.pop()
        for w,i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v,i)
            stack.append(w)
    path = 0
    w = v
    while w!= u:
        v,i = pred[w]
        w =v
        path+=1<<i
    return path

condition_path = [get_path(u,v)for u,v in uv]

s=np.zeros(1<<m,np.int64)
sgn = np.ones(1<<m,np.int64)
for i in range(m):
    s[1<<i:1<<(i+1)] = s[:1<<i] | condition_path[i]
    sgn[1<<i:1<<(i+1)]=-sgn[:1<<i]

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

n_edges = popcnt(s)

x= 1<<(n-1-n_edges)
answer =(x*sgn).sum()
print(answer)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 +7

n = int(readline())
ab = list(list(map(int,readline().split()))for _ in range(n-1))
m=int(readline())
uv=list(list(map(int,readline().split()))for _ in range(m))

graph = [[]for _ in range(n+1)]
for i ,(a,b) in enumerate(ab):
    graph[a].append((b,i))
    graph[b].append((a,i))

def get_path(U,V):
    INF = 100
    visited =[False]*(n+1)
    pred =[None]*(n+1)
    stack =[U]
    visited[U]=True
    while stack:
        v = stack.pop()
        for w,i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v,i)
            stack.append(w)
    path = 0
    w = V
    while w!= U:
        v,i = pred[w]
        w =v
        path+=1<<i
    return path

condition_path = [get_path(u,v)for u,v in uv]

s=np.zeros(1<<m,np.int64)
sgn = np.ones(1<<m,np.int64)
for i in range(m):
    s[1<<i:1<<(i+1)] = s[:1<<i] | condition_path[i]
    sgn[1<<i:1<<(i+1)]=-sgn[:1<<i]

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

n_edges = popcnt(s)

x= 1<<(n-1-n_edges)
answer =(x*sgn).sum()
print(answer)


Verdicts: Runtime Error

Accepted