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):
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, p, pre, t, edge, x):
    for nxt in G[p]:
        if nxt == pre:
            continue
        a, b = p, nxt
        if b < a:
            a, b = b, a
        if nxt == t:
            edge[(a, b)] += x
            return True
        if dfs(G, nxt, p, t, edge, x):
            edge[(a, b)] += x
            return True
    return False

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    edge = {}
    for _ in range(n-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
        if b < a:
            a, b = b, a
        edge[(a, b)] = 0
    m = int(input())
    for i in range(m):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        x = 1<<i
        dfs(G, u, -1, v, edge, x)
    ans = 2**(n-1)
    for i in range(1, 2**m):
        bit_cnt = 0
        for j in range(m):
            if (i & (1<<j)) != 0:
                bit_cnt += 1
        cnt = 0
        for v in edge.values():
            if (v & i) != 0:
                cnt += 1
        x = 2**(n-1 - cnt)
        if bit_cnt % 2 == 0:
            ans += x
        else:
            ans -= x
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        i = 0
        for x, y in edges:
            self.add_edge(x,y,i)
            i += 1
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.path_bit = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y, i):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add((y,i))
        self.edges[y].add((x,i))

    def dfs(self):
        next_set = [self.root]
        self.path_bit[self.root] = 0
        while next_set:
            p = next_set.pop()
            for q, i in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.path_bit[q] = self.path_bit[p] | 1 << i
                    self.doubling[0][q] = p
                    next_set += [q]

    def get_list(self, u, v):
        if self.decrement:
            u -= 1
            v -= 1
        return self.path_bit[u] ^ self.path_bit[v]

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.Graph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()



from itertools import combinations

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 = int(input())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))

lca = LCA(N, 1, edges, decrement=True)

M = int(input())
edges2 = []
for _ in range(M):
    x, y = map(int, input().split())
    edges2.append((x,y))

res = pow(2,N-1)
for m in range(1,M+1):
    for a in combinations(edges2, m):
        temp = 0
        for b in a:
            temp |= lca.get_list(*b)
        res += (1-2*(m%2))*pow(2,N -1 - popcnt(temp))

print(res)

Solution (Python):
from collections import defaultdict


def get_path(from_node, to_node, adj, nodes2edge):
    

    def dfs(node, parent, edges):
        if node == to_node:
            return edges
        min_path = None
        for child in adj[node]:
            if child == parent:
                continue
            path = dfs(child, node, edges + [nodes2edge[(node, child)]])
            if path is None:
                continue
            if min_path is None or len(min_path) > len(path):
                min_path = path
        return min_path

    return dfs(from_node, None, list())


def count_bits(n):
    return len([i for i in range(len('{:b}'.format(n))) if (n >> i) & 1 == 1])


def main():
    N = int(input())
    adj = defaultdict(list)
    nodes2edge = defaultdict(lambda :-1)
    for i in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
        nodes2edge[(a, b)] = i
        nodes2edge[(b, a)] = i
    M = int(input())
    constraints = [list(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(M)]
    
    base = [0] * M  
    for m, constraint in enumerate(constraints):
        u, v = constraint
        path = get_path(u, v, adj, nodes2edge)
        v = sum([2**e for e in path])
        base[m] = v
    dp = [0] * (2**M)  
    ans = 2**(N - 1)
    for S in range(1, 2**M):
        lenbit_s = len('{:b}'.format(S))
        dp[S] = dp[S - (1 << (lenbit_s - 1))] | base[lenbit_s - 1]
        cnt_s = count_bits(S)
        cnt_dp = count_bits(dp[S])
        ans += (-1)**(cnt_s % 2) * 2**(N - 1 - cnt_dp)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

import sys
input = sys.stdin.readline

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

M = int(input())
restriction = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

t = Tree(N, edge)
t.setroot(0)
t.heavylight_decomposition()

white_node = [set() for _ in range(M)]

for i in range(M):
    u, v = restriction[i]
    for lt, rt in t.range_hld(u, v, 1):
        for j in range(lt, rt):
            white_node[i].add(j)

res = 0

for bit in range(2**M):
    cnt = 0
    det = set()
    for i in range(M):
        if (bit >> i) & 1:
            cnt += 1
            det |= white_node[i]

    if cnt % 2 == 0:
        res += 2**(N - 1 - len(det))
    else:
        res -= 2**(N - 1 - len(det))

print(res)

Solution (Python):


def resolve():
    def dfs(u, v, parent):
        if u == v:
            return True
        for (to, idx) in G[u]:
            if to == parent:
                continue
            if dfs(to, v, u):
                path.append(idx)
                return True
        return False

    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(lambda x:int(x)-1, input().split())
        G[a].append((b, i))
        G[b].append((a, i))

    path = []

    M = int(input())
    cons = [0]*M
    
    for i in range(M):
        u, v = map(lambda x: int(x) - 1, input().split())
        path = []
        dfs(u, v, -1)
        for idx in path:
            cons[i] |= 1<<idx

    
    ans = 0
    for bit in range(1<<M):
        eset = 0
        for i in range(M):
            if bit>>i & 1:
                eset |= cons[i]
        white = bin(eset).count("1") 
        num = 1<<(N-1-white)
        if bin(bit).count("1") % 2 == 0:
            ans += num
        else:
            ans -= num
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):


import itertools
from collections import defaultdict
N = int(input())
G = [[] for i in range(N+1)]
edge = defaultdict(int)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[(min(a, b), max(a, b))] = i+1
    G[a].append(b)
    G[b].append(a)
M = int(input())
que = [tuple(map(int, input().split())) for i in range(M)]
Data = [set([]) for i in range(M)]


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)


for i in range(M):
    s, g = que[i]
    visited = [False for i in range(N+1)]
    parent = [-1 for i in range(N+1)]
    dfs(s)
    now = g
    while parent[now] > 0:
        number = edge[(min(now, parent[now]), max(now, parent[now]))]
        Data[i].add(number)
        now = parent[now]
ans = 2**(N-1)
seq = [i for i in range(M)]
for i in range(1, M+1):
    
    S = 0

    for v in itertools.combinations(seq, i):
        subset = set([])
        for x in v:
            subset = subset | Data[x]
        S += 2**(N-1-len(subset))
    ans -= (-1)**((i-1) % 2)*S
print(ans)

Solution (Python):

import itertools
from collections import defaultdict
N = int(input())
G = [[] for i in range(N+1)]
edge = defaultdict(int)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[(min(a, b), max(a, b))] = i+1
    G[a].append(b)
    G[b].append(a)
M = int(input())
que = [tuple(map(int, input().split())) for i in range(M)]
Data = [set([]) for i in range(M)]


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)


for i in range(M):
    s, g = que[i]
    visited = [False for i in range(N+1)]
    parent = [-1 for i in range(N+1)]
    dfs(s)
    now = g
    while parent[now] > 0:
        number = edge[(min(now, parent[now]), max(now, parent[now]))]
        Data[i].add(number)
        now = parent[now]
ans = 2**(N-1)
seq = [i for i in range(M)]
for i in range(1, M+1):
    
    S = 0
    subset = set([])
    for v in itertools.combinations(seq, i):
        subset.clear()
        for x in v:
            subset = subset | Data[x]
        S += 2**(N-1-len(subset))
    ans -= (-1)**((i-1) % 2)*S
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

def all_bit_count(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 = int(readline())
d = defaultdict(int)
cnt = 1

g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,0))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            mm = mi*100+ma
            if d[mm] == 0:
              d[mm] = cnt
              cnt += 1
            que.append((i,L|(1<<d[mm])))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = 0
    for k in j:
      K |= k
    l = all_bit_count(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n = int(readline())
g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)
  
m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,set()))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            que.append((i,L|{mi*100+ma}))
                     
import itertools

ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = set()
    for k in j:
      K |= k
    l = len(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Solution (Python):
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
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
    
m = int(input())
uvs = [None]*m
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uvs[i] = (u,v)
    
from queue import deque    
def bfs(start):
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    return seen

paths = [None]*m
for i,(u,v) in enumerate(uvs):
    seen = bfs(u)
    ss = set()
    z = v
    while z!=u:
        z1 = seen[z]
        ss.add(uv2e[z,z1])
        z = z1
    paths[i] = ss
    
ans = 0
def dfs(l, s):
    if len(l)==m:
        global ans
        val = pow(2, n-1-len(s)) * pow(-1, sum(l))
        ans += val

        return
    l.append(0)
    dfs(l, s)
    l.pop()
    
    i = len(l)
    p = paths[i]
    l.append(1)
    dfs(l, s|p)
    l.pop()
    
dfs([], set())

print(ans)

Solution (Python):
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
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
    
m = int(input())
uvs = [None]*m
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uvs[i] = (u,v)
    
from queue import deque    
def bfs(start):
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    return seen

paths = [None]*m
for i,(u,v) in enumerate(uvs):
    seen = bfs(u)
    ss = set()
    z = v
    while z!=u:
        z1 = seen[z]
        ss.add(uv2e[z,z1])
        z = z1
    paths[i] = ss
    
ans = 0
def dfs(l, s):
    if len(l)==m:
        global ans
        val = pow(2, n-1-len(s)) * pow(-1, sum(l))
        ans += val

        return
    dfs(l + [0], s)
    
    i = len(l)
    p = paths[i]
    dfs(l + [1], s|p)
    
dfs([], set())

print(ans)

Solution (Python):
from itertools import combinations
import sys

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


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 dfs(s, g):
    kouho = 0
    par = [(0, 0)] * (n + 1)
    stack = []
    stack.append(s)
    while stack:
        v = stack.pop()
        if v == g:
            break
        for u, i in graph[v]:
            if u == par[v][0]:
                continue
            par[u] = (v, i)
            stack.append(u)
    
    p = g
    q, i = par[p]
    while q > 0:
        kouho |= 1 << i
        p = q
        q, i = par[q]
    return kouho


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


sets = [0 for _ in range(m)]

for idx, (u, v) in enumerate(UV):
    sets[idx] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
    kumiawase = list(combinations(range(m), i))
    for kumi in kumiawase:
        temp = 0
        for j in range(i):
            temp |= sets[kumi[j]]
        num = popcnt(temp)
        ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    N = int(input())
    adjL = [[] for _ in range(N)]
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        adjL[a].append(b)
        adjL[b].append(a)
        edges.append((a, b))
    M = int(input())
    uvs = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

    e2Roots = [set() for _ in range(N)]
    def dfs(vNow, vPar):
        for v2 in adjL[vNow]:
            if v2 == vPar: continue
            e2Roots[v2] |= e2Roots[vNow]
            e2Roots[v2].add((vNow, v2))
            dfs(v2, vNow)

    dfs(0, -1)

    ePaths = [set() for _ in range(M)]
    for i, (u, v) in enumerate(uvs):
        ePaths[i] = e2Roots[u] ^ e2Roots[v]

    numEs = [0] * (1<<M)
    for a, b in edges:
        ptn = 0
        for iC, ePath in enumerate(ePaths):
            if (a, b) in ePath or (b, a) in ePath:
                ptn |= 1<<iC
        for S in range(1<<M):
            if S & ptn:
                numEs[S] += 1

    def getPows(base, n):
        pows = [1] * (n+1)
        for x in range(1, n+1):
            pows[x] = (pows[x-1] * base)
        return pows
    pows = getPows(2, N)

    def getNum1s(N):
        num1s = [0]
        for _ in range(N):
            num12s = [num1+1 for num1 in num1s]
            num1s += num12s
        return num1s
    num1s = getNum1s(M)

    ans = pows[N-1]
    for S in range(1, 1<<M):
        num = pows[N-1-numEs[S]]
        if num1s[S] % 2:
            ans -= num
        else:
            ans += num

    print(ans)


solve()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append((b,i))
        G[b].append((a,i))
    
    between = [[set() for _ in range(N)] for _ in range(N)]
    for i in range(N):
        stack = [(i,[])]
        while stack:
            v,before = stack.pop()
            between[i][v] = set(before)
            for e,j in G[v]:
                if e == i or len(between[i][e]) >= 1:
                    continue
                between[i][e] = set(before + [j])
                stack.append((e,before + [j]))
            
            
    
    

    M = int(input())
    condition = [tuple(map(int,input().split())) for _ in range(M)]
    condition = [(a - 1,b - 1) for a,b in condition]
    
    ans = 0
    for bit in range(1<<M):
        ret = set()
        cnt = 0
        for i in range(M):
            if (bit>>i)&1:
                cnt += 1
                ret |= between[condition[i][0]][condition[i][1]]
        
        free = N - len(ret) - 1
        
        if cnt%2 == 0:
            ans += pow(2,free)
        else:
            ans -= pow(2,free)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = int(input())
    
    
    
    


    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        for i, (a, b) in enumerate([map(int, input().split()) for i in range(N-1)]):
            edgelist[a-1].append((b-1,i))
            edgelist[b-1].append((a-1,i))
        return edgelist
    edge=tree_init(N)
    M = int(input())
    ms= tuple(tuple(map(int, input().split())) for i in range(M))
    ways=[]

    for u,v in ms:
        u-=1;v-=1
        q=deque([(u,[])])
        visited=[False]*N
        while q:
            x=q.pop()
            
            e,way=x
            if visited[e]:continue
            
            if e==v:
                ways.append(set(way))
            visited[e]=True
            for ne, j in edge[e]:
                nw=copy(way)
                nw.append(j)
                q.append((ne,nw))
                
    tot=pow(2,N-1)
    for i in range(1,M+1):
        for ws in combinations(ways,i):
            ts=set()
            for w in ws:
                ts|=w
            
            tot+=(-1)**i*pow(2,N-1-len(ts))
    print(tot)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    N = int(input())
    
    
    
    


    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        for i, (a, b) in enumerate([map(int, input().split()) for i in range(N-1)]):
            edgelist[a-1].append((b-1,i))
            edgelist[b-1].append((a-1,i))
        return edgelist
    edge=tree_init(N)
    M = int(input())
    ms= tuple(tuple(map(int, input().split())) for i in range(M))
    ways=[]

    for u,v in ms:
        u-=1;v-=1
        q=deque([(u,[])])
        visited=[False]*N
        while q:
            x=q.pop()
            
            e,way=x
            if visited[e]:continue
            
            if e==v:
                ways.append(set(way))
            visited[e]=True
            for ne, j in edge[e]:
                nw=copy(way)
                nw.append(j)
                q.append((ne,nw))
                
    tot=pow(2,N-1)
    for i in range(1,M+1):
        for ws in combinations(ways,i):
            ts=set()
            for w in ws:
                ts|=w
            
            tot+=(-1)**i*pow(2,N-1-len(ts))
    print(tot)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  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
              
  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = popcount(i) % 2
    ans += (-1)**cnt * 2**(n-1-popcount(s))
  print(ans)
  
if __name__ == "__main__":
  main()