Problem:
 Score : 600 points    Problem Statement  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.       Constraints   2 \leq N \leq 50  1 \leq a_i,b_i \leq N  The graph given in input is a tree.  1 \leq M \leq \min(20,\frac{N(N-1)}{2})  1 \leq u_i < v_i \leq N  If i \not= j , either u_i \not=u_j or v_i\not=v_j  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  a_1  b_1  :  a_{N-1}  b_{N-1}  M  u_1  v_1  :  u_M  v_M       Output  Print the number of ways to paint the edges that satisfy all of the M conditions.        Sample Input 1 3
1 2
2 3
1
1 3      Sample Output 1 3  The tree in this input is shown below:     All of the M restrictions will be satisfied if Edge 1 and 2 are respectively painted (white, black), (black, white), or (black, black), so the answer is 3 .       Sample Input 2 2
1 2
1
1 2      Sample Output 2 1  The tree in this input is shown below:     All of the M restrictions will be satisfied only if Edge 1 is painted black, so the answer is 1 .       Sample Input 3 5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5      Sample Output 3 9  The tree in this input is shown below:           Sample Input 4 8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8      Sample Output 4 62  The tree in this input is shown below:

Solution (Python):
from copy import deepcopy
from itertools import product

class EulerTour:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]
    
    def add_edge(self, a, b):
        self.G[a].append(b)
        self.G[b].append(a)
    
    def from_graph(self, G, copy=False):
        if copy: self.G = deepcopy(G)
        else: self.G = G
            
    def build(self, root=0, lca=True):
        self.root = root
        self._dfs(root)
        self.In = [0]*self.N
        self.Out = [0]*self.N
        for i, v in enumerate(self.node_list):
            if self.In[v] == 0:
                self.In[v] = i
            self.Out[v] = i
        if lca:
            self.seg = SegTree(len(self.node_list))
            self.seg.build([self.d[self.node_list[i]] for i in range(len(self.node_list))])
    
    def lca(self, a, b):
        if self.root in (a,b):
            return self.root
        a_out, b_in = self.Out[a], self.In[b]
        if a_out > b_in:
            a_out, b_in = self.Out[b], self.In[a]
        if a_out > b_in:
            a_out, b_in = self.Out[b], self.Out[a]
        if a_out > b_in:
            a_out, b_in = self.Out[a], self.Out[b]
        idx = self.seg.find(a_out, b_in+1)
        return self.node_list[idx]
            
    def _dfs(self, root=0):
        self.idx2edge = {}
        self.edge2idx = {}
        self.node_list = []
        self.edge_list = []
        seen = [0]*len(self.G)
        prev = [0]*len(self.G)
        self.d =[-1]*len(self.G)
        todo = [~root, root]
        count = 0
        while todo:
            a = todo.pop()
            if a >= 0:
                seen[a] = 1
                self.d[a] = self.d[prev[a]] + 1
                edge = (prev[a], a)
                self.idx2edge[count] = edge
                self.edge2idx[edge] = count
                self.edge_list.append(count)
                self.node_list.append(a)
                count += 1
                for b in reversed(self.G[a]):
                    if seen[b]: continue
                    todo.append(~b)
                    todo.append(b)
                    prev[b] = a
            else: 
                edge = (prev[~a], ~a)
                idx = self.edge2idx[edge]
                self.edge_list.append(-idx)
                if ~a != root: self.node_list.append(prev[~a])
                    
class SegTree:
    """ segment tree with point modification and range product. """
    
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
    
    def find(self, L, R):
        x = self.fold(L,R)
        while R-L>1:
            M = (R+L)//2
            if self.fold(L,M)==x: R = M
            else: L = M
        return L

from collections import deque

def bfs(G,s,edge2idx):
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    cumedge = [set() for _ in range(N)]
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          cumedge[b] = deepcopy(cumedge[a])
          idx = edge2idx[(a,b)]
          cumedge[b].add(idx)
    return cumedge
      
N=int(input())
et = EulerTour(N)
for i in range(N-1):
  a,b=map(int,input().split())
  et.add_edge(a-1,b-1)
  
et.build(0)
cumedge = bfs(et.G,0,et.edge2idx)

M = int(input())
path_list = [0]*M
for i in range(M):
  u,v = map(int,input().split())
  u,v = u-1,v-1
  w = et.lca(u,v)
  path_list[i] = (cumedge[u] - cumedge[w]) | (cumedge[v] - cumedge[w])

ans = 2**(N-1)
for i,p in enumerate(product(range(2),repeat=M)):
  if i == 0: continue
  union = set.union(*[path_list[i] for i in range(M) if p[i]])
  ans += (-1)**sum(p) * 2**(N-1-len(union))

print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    from itertools import combinations

    N = int(readline())

    edge = defaultdict(list)

    for i in range(N - 1):
        a, b = map(int, readline().split())
        edge[a - 1].append((b - 1, i))
        edge[b - 1].append((a - 1, i))

    def bfs(s, g):
        que = deque()
        que.append((s, []))
        visited = [False] * N
        visited[s] = True

        while que:
            cur, path = que.popleft()
            if cur == g:
                return set(path)
            for nx, i in edge[cur]:
                if not visited[nx]:
                    new_path = path + [i]
                    que.append((nx, new_path))
                    visited[nx] = True

    M = int(readline())
    constraints = []
    for _ in range(M):
        u, v = map(int, readline().split())
        u -= 1
        v -= 1
        constraints.append(bfs(u, v))

    cnt = 0
    for i in range(1, M + 1):
        sign = 1 if i % 2 == 1 else -1
        for per in combinations(range(M), r=i):
            incl = set()
            for x in per:
                incl = incl.union(constraints[x])
            cnt += sign * 2 ** ((N - 1) - len(incl))

    print(2 ** (N - 1) - cnt)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

es = []
adj = [[] for _ in range(N)]
e_index = dict()
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b))
    es.append((b, a))
    adj[a].append(b)
    adj[b].append(a)
    e_index[(a, b)] = i
    e_index[(b, a)] = i

M = int(input())
uvs = [tuple(map(int, input().split())) for _ in range(M)]

edges = [0] * (N - 1)
for i, (u, v) in enumerate(uvs):
    u -= 1
    v -= 1
    parent = [-1] * N
    stack = [u]
    while stack:
        node = stack.pop()
        if node == v:
            break

        for next_node in adj[node]:
            if parent[node] != next_node:
                parent[next_node] = node
                stack.append(next_node)
             
    node = v
    while node != u:
        next_node = parent[node]
        index = e_index[(node, next_node)]
        edges[index] |= 1 << i
        node = next_node

dp = [0] * (1 << M)
dp[0] = 1
for e in edges:
    for i in range((1 << M) - 1, -1, -1):
        dp[i | e] += dp[i]

print(dp[-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  
  
  
  S=[] 
  F=[0]*n 
  depth=[0]*n 
  def dfs(v,pare,d):
      F[v]=len(S)
      depth[v]=d
      S.append(v)
      for i,w in ki[v]:
          if w==pare:continue
          dfs(w,v,d+1)
          S.append(v)
  dfs(0,-1,0)
  
  
  
  
  
  INF = (n, None)
  
  M = 2*n
  M0 = 2**(M-1).bit_length() 
  data = [INF]*(2*M0)
  for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
  for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
  
  def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
      if b & 1:
        b -= 1
        yield data[b-1]
      if a & 1:
        yield data[a-1]
        a += 1
      a >>= 1; b >>= 1
  
  def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
      fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
  

  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1
  
  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u].union(path[v])
        tmp=tmp-path[dd]
        memo[c]=tmp
      must_w=must_w.union(tmp)
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  
  
  
  S=[] 
  F=[0]*n 
  depth=[0]*n 
  def dfs(v,pare,d):
      F[v]=len(S)
      depth[v]=d
      S.append(v)
      for i,w in ki[v]:
          if w==pare:continue
          dfs(w,v,d+1)
          S.append(v)
  dfs(0,-1,0)
  
  
  
  
  
  INF = (n, None)
  
  M = 2*n
  M0 = 2**(M-1).bit_length() 
  data = [INF]*(2*M0)
  for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
  for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
  
  def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
      if b & 1:
        b -= 1
        yield data[b-1]
      if a & 1:
        yield data[a-1]
        a += 1
      a >>= 1; b >>= 1
  
  def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
      fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
  

  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u]|path[v]
        tmp-=path[dd]
        memo[c]=tmp
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  
  
  
  S=[] 
  F=[0]*n 
  depth=[0]*n 
  def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
      if w==pare:continue
      dfs(w,v,d+1)
      S.append(v)
  dfs(0,-1,0)
  
  
  
  
  
  INF = (n, None)
  
  M = 2*n
  M0 = 2**(M-1).bit_length() 
  data = [INF]*(2*M0)
  for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
  for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
  
  def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
      if b & 1:
        b -= 1
        yield data[b-1]
      if a & 1:
        yield data[a-1]
        a += 1
      a >>= 1; b >>= 1
  
  def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
      fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
  
  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u]|path[v]
        tmp-=path[dd]
        memo[c]=tmp
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  
  
  
  S=[] 
  F=[0]*n 
  depth=[0]*n 
  def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
      if w==pare:continue
      dfs(w,v,d+1)
      S.append(v)
  dfs(0,-1,0)
  
  
  
  
  
  INF = (n, None)
  
  M = 2*n
  M0 = 2**(M-1).bit_length() 
  data = [INF]*(2*M0)
  for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
  for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
  
  def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
      if b & 1:
        b -= 1
        yield data[b-1]
      if a & 1:
        yield data[a-1]
        a += 1
      a >>= 1; b >>= 1
  
  def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
      fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
  
  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  for c in range(m):
    u,v=uv[c]
    dd=query(u,v)
    tmp=path[u]|path[v]
    tmp-=path[dd]
    memo[c]=tmp

  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      tmp=memo[c]
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  
  
  
  S=[] 
  F=[0]*n 
  depth=[0]*n 
  def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
      if w==pare:continue
      dfs(w,v,d+1)
      S.append(v)
  dfs(0,-1,0)
  
  
  
  
  
  INF = (n, None)
  
  M = 2*n
  M0 = 2**(M-1).bit_length() 
  data = [INF]*(2*M0)
  for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
  for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])
  
  def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
      if b & 1:
        b -= 1
        yield data[b-1]
      if a & 1:
        yield data[a-1]
        a += 1
      a >>= 1; b >>= 1
  
  def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
      fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
  
  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo=[set(())]*m
  for c in range(m):
    u,v=uv[c]
    dd=query(u,v)
    tmp=path[u]|path[v]
    tmp-=path[dd]
    memo[c]=tmp

  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      tmp=memo[c]
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Solution (Python):
from copy import copy
def dfs(x,v,s):
    for y,i in tree[x]:
        if parent[x] != y:
            parent[y] = x
            s.add(i)
            dfs(y,v,s)
            s.remove(i)
    if x == v:
        cons.append(s.copy())
    

N = int(input())
tree = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append((b,i))
    tree[b].append((a,i))
M = int(input())
uv = []
cons = []
for i in range(M):
    u,v =  map(int,input().split())
    uv.append((u,v))
    parent = [-1]*(N+1)
    dfs(u,v,set())
bit = [0]*(N-1)
for i in range(N):
    for j in range(M):
        if i in cons[j]:
            bit[i] += 1 << j
dp = [0]*(1 << M)
dp[0] = 1
for i in range(N-1):
    for j in range(1 << M)[::-1]:
        dp[j|bit[i]] += dp[j]
print(dp[-1])

Solution (Python):
from itertools import product

N = int(input())
ab = [tuple(map(int, input().split())) for _ in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]


class Node:
    def __init__(self, nodeid, parent=None):
        self.nodeid = nodeid
        self.parent = parent
        self.children = []

    def add_child(self, nodeid, edgeid):
        child = Node(nodeid, parent=self)
        self.children.append((child, edgeid))

    def parents(self):
        if self.parent == None:
            return [self.nodeid]
        else:
            return [self.nodeid] + self.parent.parents()

    def path(self, to):
        if to == self.nodeid:
            return []
        for child, edgeid in self.children:
            try:
                ret = [edgeid] + child.path(to)
                return ret
            except ValueError:
                pass
        raise ValueError


root = Node(1)
nodes = {1: root}
leef = [root]
while len(leef) > 0:
    node = leef.pop()
    parentid = node.parent and node.parent.nodeid
    for i, (a, b) in enumerate(ab):
        if a == node.nodeid and b != parentid:
            node.add_child(b, i)
            leef.append(node.children[-1][0])
            nodes[b] = node.children[-1][0]
        elif b == node.nodeid and a != parentid:
            node.add_child(a, i)
            leef.append(node.children[-1][0])
            nodes[a] = node.children[-1][0]


constraints = [0]*M

for i, (u, v) in enumerate(uv):
    parents_u = nodes[u].parents()
    for p in nodes[v].parents():
        if p in parents_u:
            break
    for j in nodes[p].path(u):
        constraints[i] += pow(2, j)
    for j in nodes[p].path(v):
        constraints[i] += pow(2, j)

ans = 0
for idx in product([True, False], repeat=M):
    sumidx = sum(idx)
    constraint = 0
    for i, flg in enumerate(idx):
        if flg:
            constraint = constraint | constraints[i]
    C = bin(constraint)[2:].count('1')
    ans += pow(2, N-1-C) * ((-1)**(sumidx%2))

print(ans)

Solution (Python):
import numpy as np

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

    
def solve(N, M, Ok):
    def solve_half(Ok_half):
        
        n = len(Ok_half)
        res = [0] * (1<<M)
        for set_black in range(1<<n):
            r = 0
            for i, Ok_i in enumerate(Ok_half):
                if set_black>>i&1:
                    r |= Ok_i
            res[r] += 1
        return res

    A = solve_half(Ok[:(N-1)//2])
    B = solve_half(Ok[(N-1)//2:])

    def fwt(A):
        n = len(A)
        
        for i in range(int(np.log2(n))):
            i = 1<<i
            for j in range(n):
                if i&j == 0:
                    A[j|i] += A[j]
        return A

    def ifwt(A):
        n = len(A)
        
        for i in range(int(np.log2(n))):
            i = 1<<i
            for j in range(n):
                if i&j == 0:
                    A[j|i] -= A[j]
        return A

    A = fwt(A)
    B = fwt(B)
    AB = [a*b for a, b in zip(A, B)]
    AB = ifwt(AB)
    return AB[-1]

numba_compile([
    [solve, "i8(i8,i8,i8[:])"],
])

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    Edges = []
    for _ in range(N - 1):
        a, b = sorted(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        Edges.append((a, b))

    def dfs(v, target, p, Path):
        if v == target:
            Path.append(v)
            return True
        for u in G[v]:
            if p != u:
                f = dfs(u, target, v, Path)
                if f:
                    Path.append(v)
                    return True
        return False

    M = int(input())
    UV = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
    Ok = [0] * (N - 1)
    for idx_UV, (a, b) in enumerate(UV):
        Path = []
        dfs(a, b, -1, Path)
        for v, u in zip(Path, Path[1:]):
            v, u = sorted([v, u])
            idx_Edge = Edges.index((v, u))
            Ok[idx_Edge] |= 1 << idx_UV
    print(solve(N, M, np.array(Ok, dtype=np.int64)))

main()

Solution (Python):

import sys
def I():
    return int(sys.stdin.readline().rstrip())

def MI():
    return map(int, sys.stdin.readline().rstrip().split())


def main():
    N = I()
    dist = [[100] * (N + 1) for _ in range(N + 1)]  
    edges = {}

    for i in range(N - 1):
        a, b = MI()
        dist[a][b] = 1
        dist[b][a] = 1
        edges[(a, b)] = i
        edges[(b, a)] = i

    for i in range(1, N + 1):
        dist[i][i] = 0

    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    M = I()
    A = []  
    for _ in range(M):
        u, v = MI()
        B = set()
        while True:
            if dist[u][v] == 1:
                B.add(edges[(u, v)])
                break
            else:
                for i in range(1, N + 1):
                    if dist[u][i] == dist[u][v] - 1 and dist[i][v] == 1:
                        B.add(edges[(i, v)])
                        v = i
                        break
        A.append(B)

    

    ans = 0
    for i in range(2 ** M):
        C = set()
        a = 0
        for j in range(M):
            if (i >> j) & 1:
                C |= A[j]
                a += 1
        l = len(C)
        a %= 2
        ans += (-1) ** a * 2 ** (N - 1 - l)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    def I():
        return int(sys.stdin.readline().rstrip())

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    N = I()
    dist = [[100] * (N + 1) for _ in range(N + 1)]  
    edges = {}

    for i in range(N - 1):
        a, b = MI()
        dist[a][b] = 1
        dist[b][a] = 1
        edges[(a, b)] = i
        edges[(b, a)] = i

    for i in range(1, N + 1):
        dist[i][i] = 0

    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    M = I()
    A = []  
    for _ in range(M):
        u, v = MI()
        B = set()
        while True:
            if dist[u][v] == 1:
                B.add(edges[(u, v)])
                break
            else:
                for i in range(1, N + 1):
                    if dist[u][i] == dist[u][v] - 1 and dist[i][v] == 1:
                        B.add(edges[(i, v)])
                        v = i
                        break
        A.append(B)

    

    ans = 0
    for i in range(2 ** M):
        C = set()
        a = 0
        for j in range(M):
            if (i >> j) & 1:
                C |= A[j]
                a += 1
        l = len(C)
        a %= 2
        ans += (-1) ** a * 2 ** (N - 1 - l)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
dist = [[100]*(N+1) for _ in range(N+1)]  
edges = {}

for i in range(N-1):
    a,b = MI()
    dist[a][b] = 1
    dist[b][a] = 1
    edges[(a,b)] = i
    edges[(b,a)] = i

for i in range(1,N+1):
    dist[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

M = I()
A = []  
for _ in range(M):
    u,v = MI()
    B = set()
    while True:
        if dist[u][v] == 1:
            B.add(edges[(u,v)])
            break
        else:
            for i in range(1,N+1):
                if dist[u][i] == dist[u][v]-1 and dist[i][v] == 1:
                    B.add(edges[(i,v)])
                    v = i
                    break
    A.append(B)


def popcount(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




ans = 0
for i in range(2**M):
    C = set()
    for j in range(M):
        if (i >> j) & 1:
            C |= A[j]
    l = len(C)
    a = popcount(i)
    a %= 2
    ans += (-1)**a * 2**(N-1-l)

print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
dist = [[100]*(N+1) for _ in range(N+1)]  
edges = {}

for i in range(N-1):
    a,b = MI()
    dist[a][b] = 1
    dist[b][a] = 1
    edges[(a,b)] = i
    edges[(b,a)] = i

for i in range(1,N+1):
    dist[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

M = I()
A = []  
for _ in range(M):
    u,v = MI()
    B = set()
    while True:
        if dist[u][v] == 1:
            B.add(edges[(u,v)])
            break
        else:
            for i in range(1,N+1):
                if dist[u][i] == dist[u][v]-1 and dist[i][v] == 1:
                    B.add(edges[(i,v)])
                    v = i
                    break
    A.append(B)



ans = 0
for i in range(2**M):
    C = set()
    a = 0
    for j in range(M):
        if (i >> j) & 1:
            C |= A[j]
            a += 1
    l = len(C)
    a %= 2
    ans += (-1)**a * 2**(N-1-l)

print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
dist = [[100]*(N+1) for _ in range(N+1)]  
edges = {}

for i in range(N-1):
    a,b = MI()
    dist[a][b] = 1
    dist[b][a] = 1
    edges[(a,b)] = i
    edges[(b,a)] = i

for i in range(1,N+1):
    dist[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

M = I()
A = []  
for _ in range(M):
    u,v = MI()
    B = set()
    while True:
        if dist[u][v] == 1:
            B.add(edges[(u,v)])
            break
        else:
            for i in range(1,N+1):
                if dist[u][i] == dist[u][v]-1 and dist[i][v] == 1:
                    B.add(edges[(i,v)])
                    v = i
                    break
    A.append(B)



ans = 0
for i in range(2**M):
    C = set()
    a = 0
    for j in range(M):
        if (i >> j) & 1:
            C = C | A[j]
            a = 1-a
    l = len(C)
    if a == 0:
        ans += pow(2,N-1-l)
    else:
        ans -= pow(2,N-1-l)

print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

def popcnt(x):
    c = 0
    while x>0:
        c += x%2
        x >>= 1
    return c

def dfs(u,v,p):
    global d
    d[u][v] = p
    for x in dst[v]:
        if u!=x and d[u][x]==0:
            p |= 1<<dst[v][x]
            dfs(u,x,p)
            p ^= 1<<dst[v][x]

n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    a,b = inm()
    dst[a][b] = dst[b][a] = i

m = inn()
u = []
v = []
for i in range(m):
    uu,vv = inm()
    u.append(uu)
    v.append(vv)

if False and n==2 and m==1:
    print(0)
    exit()

d = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    dfs(i,i,0)
dd = []
for i in range(m):
    dd.append(d[u[i]][v[i]])
ddprint(dst)
ddprint(d)
ddprint(u)
ddprint(v)
ddprint(dd)

y = 0
for i in range(1,2**m):
    nbits = x = 0
    for j in range(m):
        if (i>>j)%2>0:
            x |= dd[j]
            nbits += 1
    nsegs = popcnt(x)
    s = 2*(nbits%2)-1
    y += s*2**(n-1-nsegs)
print(2**(n-1)-y)