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
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

    """
    一般に頂点vと頂点tvの間の辺を出力する再帰関数dfsを用意する。
    頂点vからdfsしたとして、頂点tvにたどり着いたところから再帰がスタート。
    まず辺を格納するedgesを空にして、dfs(e[0], tv, v)が成り立つなら
    v-...-e-tvのパスが確定しているのでeとtvを繋ぐパスe[1]をedgeに加える。
    これを順に再帰で繰り返す。
    """
    edges = []
    def dfs(v, tv, p=-1):
        if v == tv:
            edges[:] = []
            return True
        for e in repn[v]:
            if e[0] == p:
                continue
            if dfs(e[0], tv, v):
                edges.append(e[1])
                return True
        return False

    """
    M個の各条件に対してパスの情報を記録するのにはビットを用いると良い。
    具体的にはedgesetと言うM個の整数配列を用意して、i番目のクエリに対して
    uiとviを繋ぐ辺が[ej1,ej2,...,ejk]だったとすると、これはedgeset[i]の
    j1,j2,...,jk番目のビットを立てて保持しておく。
    　→　あとで包除原理する際に楽。
    """

    edgeset = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        dfs(u - 1, v - 1)
        for id in edges:
            edgeset[i] |= 1 << id

    """
    ここから包除原理。M個の条件のうちどの条件だけを考慮するかは(1 << M)通りの選択があることに注意。
    """

    ans = 0
    for i in range(1 << M):
        mask = 0
        for j in range(M):
            if (i >> j) & 1:
                mask |= edgeset[j]
        white = bin(mask).count("1")
        val = 1 << (N - 1 - white)
        if bin(i).count("1") % 2 == 0:
            ans += val
        else:
            ans -= val
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    edge_to_idx = {}
    for i in range(n - 1):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        E[u].append(v)
        E[v].append(u)
        edge_to_idx[u, v] = edge_to_idx[v, u] = i

    def path(source, target):
        par = [-1] * n
        stack = [(source, -1)]
        while stack:
            v, p = stack.pop()
            for nv in E[v]:
                if nv == p:
                    continue
                par[nv] = v
                stack.append((nv, v))
        res = 0
        while target != source:
            res |= 1 << edge_to_idx[target, par[target]]
            target = par[target]
        return res

    m = int(input())
    constraints = [None] * m
    for i in range(m):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        constraints[i] = path(u, v)

    res = 1 << (n - 1)
    
    for U in range(1, 1 << m):
        coef = 1 if bin(U).count('1') & 1 else -1
        binary = 0
        for i in range(m):
            if (U >> i) & 1:
                binary |= constraints[i]
        cnt = (n - 1) - bin(binary).count('1')
        res -= coef * (1 << cnt)

    print(res)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    edge_to_idx = {}
    for i in range(n - 1):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        E[u].append(v)
        E[v].append(u)
        edge_to_idx[u, v] = edge_to_idx[v, u] = i

    def path(v, p, target):
        
        if v == target:
            return 1 << edge_to_idx[v, p]
        res = 0
        for nv in E[v]:
            if nv == p:
                continue
            res |= path(nv, v, target)
        if res > 0 and p != -1:
            res |= 1 << edge_to_idx[v, p]
        return res

    m = int(input())
    constraints = [None] * m
    for i in range(m):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        constraints[i] = path(u, -1, v)

    res = 1 << (n - 1)
    
    for U in range(1, 1 << m):
        coef = 1 if bin(U).count('1') & 1 else -1
        binary = 0
        for i in range(m):
            if (U >> i) & 1:
                binary |= constraints[i]
        cnt = (n - 1) - bin(binary).count('1')
        res -= coef * (1 << cnt)

    print(res)
resolve()

Solution (Python):





def main():
    from collections import namedtuple
    from functools import reduce
    from itertools import combinations
    from operator import or_

    Edge = namedtuple('Edge', 'to edge_id')

    def bit_path(curr, goal, par=-1):
        if curr == goal:
            return 0
        for e in g[curr]:
            if e.to == par: continue
            res = bit_path(curr=e.to, goal=goal, par=curr)
            if ~res:  
                return res | (1 << e.edge_id)
        return -1

    def popcnt(n):
        """https://atcoder.jp/contests/abc152/submissions/9619555"""
        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())

    g = tuple(set() for _ in range(N))
    for edge_id in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(Edge(to=b, edge_id=edge_id))
        g[b].add(Edge(to=a, edge_id=edge_id))

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    ans = 1 << (N - 1)
    for k in range(1, M + 1):
        for comb in combinations(cons, r=k):
            b = reduce(or_, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - popcnt(b)))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import namedtuple
    from functools import reduce
    from itertools import combinations
    from operator import or_

    Edge = namedtuple('Edge', 'to edge_id')

    def bit_path(curr, goal, par=-1):
        if curr == goal:
            return 0
        for e in g[curr]:
            if e.to == par: continue
            res = bit_path(curr=e.to, goal=goal, par=curr)
            if ~res:  
                return res | (1 << e.edge_id)
        return -1

    N = int(input())

    g = tuple(set() for _ in range(N))
    for edge_id in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(Edge(to=b, edge_id=edge_id))
        g[b].add(Edge(to=a, edge_id=edge_id))

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    ans = 1 << (N - 1)
    for k in range(1, M + 1):
        for comb in combinations(cons, r=k):
            b = reduce(or_, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - bin(b).count('1')))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
m = int(input())
uv = [list(map(int,input().split())) for _ in range(m)]

from collections import deque

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

def bfs(start,end):
    parent = [[-1,-1] for _ in range(n+1)]
    d = deque()
    d.append(start)
    done = set()
    while(d):
        tmp = d.popleft()
        done.add(tmp)
        for i in links[tmp]:
            link_ind, j = i
            if(not j in done):
                parent[j] = [tmp,link_ind]
                d.append(j)
    route = []
    while(True):
        route.append(parent[end][1])
        end = parent[end][0]
        if(end == start):
            break
    return route[::-1]

links_key = [0] * (n-1)
for i,se in enumerate(uv):
    start,end = se
    route = bfs(start,end)
    for j in route:
        links_key[j] =(links_key[j] | 1<<i)

dp = [[0] * (2**m) for _ in range(n)]
dp[0][0] = 1

for i in range(n-1):
     for j in range(2**m):
         dp[i+1][j] += dp[i][j]
         dp[i+1][(j|links_key[i])] += dp[i][j]

print(dp[-1][-1])

Solution (Python):
def examA():
    N = I()
    L = LI()
    L.sort()
    if sum(L)<=L[-1]*2:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, M = LI()
    A = [LI()for _ in range(N)]
    A.sort(key=lambda x:x[0])
    ans = 0
    for a,b in A:
        if M<=b:
            ans += a*M
            break
        ans += a*b
        M -= b
    print(ans)
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    D = defaultdict(int)
    for s in S:
        cur = []
        for i,j in Counter(s).items():
            cur.append((i,j))
        
        cur.sort()
        cur = tuple(cur)
        D[cur] += 1
    ans = 0
    for d in D.values():
        ans += (d-1)*d//2
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+A[i]
    ans = 0
    for i in range(N):
        l = i-1; r = N
        if S[-1]-S[i]<K:
            break
        while(r-l>1):
            now = (l+r)//2
            if S[now]-S[i]<K:
                l = now
            else:
                r = now
        
        ans += (N-r+1)
    print(ans)
    return

def examE():
    
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            
            self.ide_ele = ele
            self.segfun = segfun
            
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret

    N, D, A = LI()
    X = [LI()for _ in range(N)]
    X.sort()
    L = [0]*N
    for i in range(N):
        L[i] = X[i][0]
    S = SegmentTree(N,0,lambda a, b: a+b)
    ans = 0
    for i,[x,h] in enumerate(X):
        H = h - S.query(i)
        if H<=0:
            continue
        ne = bisect.bisect_right(L,x+2*D)
        
        need = (H-1)//A + 1
        S.update(i,ne,need*A)
        ans += need
    print(ans)
    return

def examF():
    N = I()
    V = [[]for _ in range(N)]
    Num_edge = {}
    for i in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
        Num_edge[(a,b)] = i
        Num_edge[(b,a)] = i
    def dfs(S,s,p,g):
        now = s
        neS = []
        if now==g:
            return S
        for ne in V[now]:
            if ne==p:
                continue
            neS = dfs(S+(1<<Num_edge[(now,ne)]),ne,now,g)
            if neS:
                return neS
        return
    M = I()
    Q = [0]*M

    for i in range(M):
        a, b = LI()
        a -= 1; b -= 1
        Q[i] = dfs(0,a,-1,b)
    
    ans = pow(2,N-1)
    loop = 2**M
    for i in range(1,loop):
        cur = 0
        num = 0
        for k in range(M):
            if i&(1<<k)>0:
                num += 1
                cur |= Q[k]
        
        if num%2==1:
            ans -= 1 << (N - 1 - bin(cur).count("1"))
        else:
            ans += 1 << (N - 1 - bin(cur).count("1"))
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):

from collections import deque

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

def bfs(s:int, g:int):
    """ 始点sから終点gまでのパスを求める """
    in_edge = [-1] * N
    par = [-1] * N
    flag = False 
    
    que = deque([s])
    while que:
        v = que.popleft()
        for w, n in edge[v]:
            if w == par[v]: continue
            in_edge[w] = n
            par[w] = v
            if w == g:
                flag = True
                break
            que.append(w)
        if flag: break
    path = 0
    cur = g
    while in_edge[cur] >= 0:
        path |= 1 << in_edge[cur]
        cur = par[cur]
    return path


M = int(input())
path = [0] * M 
for i in range(M):
    u,v = map(int, input().split())
    path[i] = bfs(u - 1, v - 1)

ans = 0

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

print(ans)

Solution (Python):

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def main():
    import sys
    import collections
    input = sys.stdin.readline
    N = int(input())
    G = [[-1]*N for i in range(N)]

    ans = 2**(N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = i
        G[b][a] = i
    ans = 0
    g = [[0]*N for i in range(N)]
    for i in range(N):
        q = collections.deque()
        q.append((i, 0))
        r = [True]*N
        r[i] = False
        while(q):
            x, s = q.popleft()
            for y in range(N):
                if G[x][y] >= 0 and r[y]:
                    g[i][y] = s | 1 << G[x][y]
                    q.append((y, g[i][y]))
                    r[y] = False
    M = int(input())
    s = [0 for i in range(M)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1

        s[i] = g[u][v]

    
    for i in range(2**M):
        tmp = 2**(N-1) - 1
        c = 0
        for j in range(M):
            if (i >> j) % 2 == 1:
                tmp &= ~s[j]
                c += 1
        ans += ((-1)**(c))*(1 << popcount(tmp))

    print(ans)


main()

Solution (Python):

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def main():
    import collections
    N = int(input())
    G = [[-1]*N for i in range(N)]

    ans = 2**(N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = i
        G[b][a] = i
    ans = 0
    g = [[0]*N for i in range(N)]
    for i in range(N):
        q = collections.deque()
        q.append((i, 0))
        r = [True]*N
        r[i] = False
        while(q):
            x, s = q.popleft()
            for y in range(N):
                if G[x][y] >= 0 and r[y]:
                    g[i][y] = s | 1 << G[x][y]
                    q.append((y, g[i][y]))
                    r[y] = False
    M = int(input())
    s = [0 for i in range(M)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1

        s[i] = g[u][v]

    
    for i in range(2**M):
        tmp = 2**(N-1) - 1
        c = 0
        for j in range(M):
            if (i >> j) % 2 == 1:
                tmp &= ~s[j]
                c += 1
        ans += ((-1)**(c))*(1 << popcount(tmp))

    print(ans)


main()

Solution (Python):
from collections import deque
def solve(s, t):
    par = {}
    par[s] = -1
    q = deque([s])
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if nxt_v in par:
                continue
            else:
                q.append(nxt_v)
                par[nxt_v] = v
    res = []
    while True:
        if par[t] != -1:
            res.append(edge[min(t, par[t]), max(t, par[t])])
            t = par[t]
        else:
            return res
    
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
const = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
edge = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    edge[min(a, b), max(a, b)] = i
    tree[a].append(b)
    tree[b].append(a)
    
bit_v = [0] * m
for i in range(m):
    s, t = const[i]
    s -= 1
    t -= 1
    bit_state = 0
    for mask in solve(s, t):
        bit_state |= (1 << mask)
    bit_v[i] = bit_state

ans = 0
for bit_state in range(1, 1 << m):
    bit_cnt = bin(bit_state).count("1")
    mask = 0
    for i in range(m):
        if bit_state & (1 << i):
            mask |= bit_v[i]
    if bit_cnt % 2 == 0:
        ans -= 2 ** (n - 1 - bin(mask).count("1"))
    else:
        ans += 2 ** (n - 1 - bin(mask).count("1"))
print(2 ** (n - 1) - ans)

Solution (Python):
from itertools import combinations

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

adj = [[] for _ in range(n)]
ids = [[-1] * n for _ in range(n)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    ids[a][b] = i
    ids[b][a] = i


def dfs(s, g):
    d = [-1] * n
    d[s] = 0
    p = [-1] * n
    stack = [s]

    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    v = g
    ret = 0
    while v != s:
        i = ids[v][p[v]]
        ret += 1 << i
        v = p[v]

    return ret


def bin_count(tpl):
    sm_or = 0
    for e in tpl:
        sm_or |= e

    return bin(sm_or).count("1")


path = [dfs(u - 1, v - 1) for u, v in uv]
ex = 0
for i in range(1, m + 1):
    for tpl in combinations(path, i):
        ex += pow(2, n - 1 - bin_count(tpl)) * (-1) ** (i % 2 + 1)

ans = pow(2, n - 1) - ex
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    m=int(input())
    C=[]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        C.append((u,v))
    
    def normalized(u,v):
        return (min(u,v),max(u,v))
    def findpath(u,v,visited=None):
        if visited is None:
            visited=set()
        if u==v:
            return set()
        if u in visited:
            return None
        visited.add(u)
        for x in Edges[u]:
            P=findpath(x,v,visited)
            if P is not None:
                P.add(normalized(u,x))
                return P
    def set_path(Pairs,Paths):
        if len(Pairs)<=1:
            yield ((Pairs[0],),Paths[Pairs[0]])
            yield ((),set())
        else:
            for S,P in set_path(Pairs[1:],Paths):
                yield ((Pairs[0],)+S,P|Paths[Pairs[0]])
                yield (S,P)
    
    Paths={}
    for u,v in C:
        Paths[(u,v)]=findpath(u,v)
    ans=pow(2,(n-1))
    for S,P in set_path(C,Paths):
        l=len(S)
        if l<=0:
            continue
        c=pow(2,(n-1)-len(P))
        flag=1 if l%2==0 else -1
        ans+=flag*c
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    def dfs(p, g, pre=-1):
        for e in edg[p]:
            if e == pre: continue
            if e == g:
                return [d[(p, e)]]
            tmp = dfs(e, g, p)
            if tmp:
                return tmp + [d[(p, e)]]
        return False

    n = II()
    edg = [[] for i in range(n)]
    t = 0
    ab = defaultdict(int)
    d = defaultdict(int)
    for _ in range(n - 1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
        d[(a, b)] = t
        d[(b, a)] = t
        t += 1
    m = II()
    path = [0] * m 
    uv = LIR_(m)
    for i, uvi in enumerate(uv):
        u, v = uvi
        pat = dfs(u,v)
        for p in pat:
            path[i] |= 1 << p
    ans = 1 << (n - 1)
    for mask in range(1, 1 << m):
        tmp = 0
        t = 0
        for i in range(m):
            if mask & (1 << i):
                t += 1
                tmp = tmp | path[i]
        x = 0
        while tmp:  
            x += tmp & 1
            tmp >>=1
        ans += (1 << (n - x - 1)) * (-1) ** t
    print(ans)


    return



if __name__ == '__main__':
    solve()

Solution (Python):
from collections import *

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 i in range(N)]
edge_id = defaultdict(lambda : -1)
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)
    edge_id[(a, b)] = edge_id[(b, a)] = i
path = defaultdict(lambda : -1)

def set_path(r, v, path_):
    visited[v] = 1
    path[(r, v)] = path_
    for u in edges[v]:
        if visited[u] == 0:
            set_path(r, u, path_ | (1 << edge_id[(v, u)]))

for i in range(N):
    visited = [0] * N
    set_path(i, i, 0)
M = int(input())
uv = [list(map(lambda x: int(x)-1, input().split())) for i in range(M)]
ans = pow(2, N-1)
for i in range(1, 1 << M):
    all_path = 0
    for j, (u, v) in enumerate(uv):
        if i & (1 << j):
            all_path |= path[(u, v)]
    if popcnt(i) & 1:
        ans -= pow(2, N-1-popcnt(all_path))
    else:
        ans += pow(2, N-1-popcnt(all_path))
print(ans)

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()

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()

  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 = bin(i).count("1") % 2
    ans += (-1)**cnt * 2**(n-1-bin(s).count("1"))
  print(ans)
  
if __name__ == "__main__":
  main()

Solution (Python):
def DFS(graph,root,parent):
  dist = [-1]*(n+1)
  dist[root] = 0
  stack = [root]
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        parent[y] = x
        dist[y] = dist[x]+1
        stack.append(y)
  return dist


class Doubling:
  def __init__(self,graph,root):
    self.root = root
    n = len(graph)-1
    self.ancestor_ls = [[0]*(n+1)]
    self.distance = DFS(graph,root,self.ancestor_ls[0])
    self.bitn = n.bit_length()
    for i in range(1,self.bitn+1):
      ancestor_ls_app = [0]*(n+1)
      for j in range(1,n+1):
        ancestor_ls_app[j] = self.ancestor_ls[i-1][self.ancestor_ls[i-1][j]]
      self.ancestor_ls.append(ancestor_ls_app)
  
  def dist(self):
    return self.distance
  
  def parent(self):
    return self.ancestor_ls[0]

  def ancestor(self,v,depth):
    if depth == 0:
      return v
    if n<depth:
      return self.root
    ret = v
    for i in range(self.bitn):
      if depth&1<<i:
        ret = self.ancestor_ls[i][ret]
    return ret
  
  def LCA(self,u,v):
    if self.distance[u]<self.distance[v]:
      u,v = v,u
    dif = self.distance[u]-self.distance[v]
    w = self.ancestor(u,dif)
    if w == v:
      return v
    for i in range(self.bitn,-1,-1):
      if self.ancestor_ls[i][w] != self.ancestor_ls[i][v]:
        w,v = self.ancestor_ls[i][w],self.ancestor_ls[i][v]
    return self.ancestor_ls[0][v]

import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)

sol = Doubling(graph,1)
pls = sol.parent()

m = int(input())
cons = [0 for i in range(m)]
for i in range(m):
  u,v = map(int,input().split())
  lca = sol.LCA(u,v)
  while u != lca:
    cons[i] |= 1<<u
    u = pls[u]
  while v != lca:
    cons[i] |= 1<<v
    v = pls[v]
ans = 0
for i in range(2**m):
  x = 0
  for j in range(m):
    if i & 1<<j:
      x |= cons[j]
  bcnt = 0
  for j in range(n+1):
    if x & 1<<j:
      bcnt += 1
  if bin(i).count("1")%2 == 1:
    ans -= 2**(n-1-bcnt)
  else:
    ans += 2**(n-1-bcnt)
print(ans)