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**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    
    root = 0
    q = []
    q.append(root)
    pre = [-1]*N
    visited = [False]*N
    while q:
        v = q.pop() 
        visited[v] = True
        for to in edge[v]:
            if visited[to]:
                continue
            pre[to] = v
            q.append(to)
    
    path = [] 
    constraint = []
    M=I()
    for i in range(M):
        a,b = MI_()
        constraint.append((a,b))

        
        root_path_a = 1<<a
        root_path_b = 1<<b
        
        while a!=root:
            root_path_a |= 1<<pre[a]
            a = pre[a]
        while b!=root:
            root_path_b |= 1<<pre[b]
            b = pre[b]
        path.append(root_path_a ^ root_path_b) 
        if not path[-1]>>a&1:
            path[-1] |= 1<<a
        if not path[-1]>>b&1:
            path[-1] |= 1<<b
    

    ans = 0
    for mask in range(1<<M):
        builtin_count = 0
        U = 0 
        for i in range(M):
            if mask>>i&1:
                builtin_count += 1
                U |= path[i]
        edge_cnt = max(0,bin(U).count("1")-1)
        if builtin_count&1:
            ans -= 1<<(N-1-edge_cnt)
        else:
            ans += 1<<(N-1-edge_cnt)
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
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)]
route = [[] for _ in range(N)]

for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    route[a].append((b, i))
    route[b].append((a, i))

path = [0] * M
for i, (u, v) in enumerate(uv):
    u -= 1
    v -= 1
    stack = [u]
    visited = [0] * N
    visited[u] = 1
    dire = [[] for _ in range(N)]
    while True:
        s = stack.pop()
        for g, j in route[s]:
            if visited[g]:
                continue   
            stack.append(g)
            dire[g].append((s, j))
            visited[g] = 1
        if visited[v]:
            break
    s = v
    while True:
        g, num = dire[s][0]
        path[i] |= (1 << num)
        if g == u:
            break
        s = g

data = [0] * (1 << M)
ans = 2 ** (N - 1)
for i in range(1, 1 << M):
    k = len(bin(i)) - 3
    data[i] = data[i - (2 ** k)] | path[k]
    power = bin(data[i]).count("1")
    judge = bin(i).count("1")
    ans += (-2 ** (N - 1 - power) if judge % 2 else 2 ** (N - 1 - power))
print(ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

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

if __name__ == '__main__':
    main()

Solution (Python):

N, = map(int, input().split())
G = [set() for _ in range(N+1)]
d = dict()
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)
    d[(a,b)] = i
    d[(b,a)] = i
ps = []
M, = map(int, input().split())
for _ in range(M):
    a, b = map(int, input().split())
    stack = [a]
    path = []
    vs = set([a])
    while stack:
        v = stack.pop()
        if v > 0:
            path.append(v)
            if v == b:
                break
            vs.add(v)
            for u in G[v]:
                if u in vs:
                    continue
                vs.add(u)
                stack += [-v, u]
        else:
            path.pop()
    es = 0
    for i in range(len(path)-1):
        es += 1<<d[(path[i], path[i+1])]
    ps.append(es)

r=0
for i in range(2**M):
    p=m=j=0
    x=0
    while i:
        if i%2:
            x=x|ps[j]
            p+=1
        i >>= 1
        j+=1
    r+=(-1 if p%2 else 1)*(1<<(N-1-bin(x).count("1")))
print(r)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
    x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
    x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
    x = (x & 0x0000ffff0000ffff) + (x >>16 & 0x0000ffff0000ffff);
    return (x & 0x00000000ffffffff) + (x >>32 & 0x00000000ffffffff);

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-bin(s).count('1'))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = set()
        v = g
        while v != s:
            v, i = par[v]
            r.add(i)
        return r
    
    M = int(input())
    path = [None] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-len(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = set()
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = set()
        v = g
        while v != s:
            v, i = par[v]
            r.add(i)
        return r
    
    M = int(input())
    path = [None] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-len(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = bin(p).count('1') & 1
        s = set()
        for i in range(M):
            if p&1: s |= path[i]
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    n = int(input())
    edge = []
    edge_id = []
    for i in range(n):
        edge.append([])
        edge_id.append(dict())
    for i in range(n-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        edge_id[a-1].update({b-1: i})
        edge_id[b-1].update({a-1: i})
    m = int(input())
    uv = []
    for i in range(m):
        uv.append(list(map(int, input().split())))

    edge_mask = []
    for i in range(m):
        distance_from_u = []
        visited = []
        for j in range(n):
            distance_from_u.append(0)
            visited.append(False)
        que = deque()
        que.append([uv[i][0]-1, 0])
        while len(que) > 0:
            now, dist = que.popleft()
            if visited[now]:
                continue
            visited[now] = True
            distance_from_u[now] = dist
            for x in edge[now]:
                if not visited[x]:
                    que.append([x, dist+1])
        next = uv[i][1]-1
        edge_set = set()
        while distance_from_u[next] > 0:
            for x in edge[next]:
                if distance_from_u[x] < distance_from_u[next]:
                    edge_set.add(edge_id[next][x])
                    next = x
                    break
        edge_mask.append(edge_set)

    dp_mask = []
    for i in range(n-1):
        new_mask = 0
        for j in range(m):
            if i in edge_mask[j]:
                new_mask = new_mask | (1 << j)
        dp_mask.append(new_mask)

    dp = []
    for i in range(n):
        dp.append([])
        for j in range(1 << m):
            dp[i].append(0)
    dp[0][0] = 1
    for i in range(n-1):
        for j in range(1 << m):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j|dp_mask[i]] += dp[i][j]

    ans = dp[n-1][(1<<m)-1]

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from scipy.sparse.csgraph import dijkstra
from itertools import combinations

N = int(input())
edge_id = {}
D = [[-float('inf')]*N for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1][b-1] = D[b-1][a-1] = 1
  edge_id[(a-1, b-1)] = i
  edge_id[(b-1, a-1)] = i

paths = dijkstra(D, return_predecessors=True)[1]
M = int(input())
edges = [0] * M
for i in range(M):
  u, v = map(int, input().split())
  now, p = paths[u-1][v-1], v-1
  edges[i] += 1 << edge_id[(now, p)]
  while now != u-1:
    now, p = paths[u-1][now], now
    edges[i] += 1 << edge_id[(now, p)]

ans = pow(2, N-1)
coeff = -1
for m in range(1, M+1):
  for comb in combinations(edges, m):
    e = 0
    for c in comb:
      e |= c
    ans +=  coeff* pow(2, N-1-bin(e).count('1'))
  coeff *= -1

print(ans)

Solution (Python):
import sys
from collections import defaultdict as dd
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
el = []
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  if u > v: u, v = v, u
  el.append((u, v))

vis = []
def dfs(s, t):
  global vis
  vis.append(s)
  if s == t:
    res = list(vis)
    vis.remove(s)
    return res
  res = []
  for x in e[s]:
    if x in vis: continue
    tt = dfs(x, t)
    if len(tt):
      res = tt
      break
  vis.remove(s)
  return res


M = int(input())
table = [[0] * (N - 1) for _ in range(M)]
for i in range(M):
  u, v = map(int, input().split())
  p = dfs(u, v)
  
  for j in range(len(p) - 1):
    for k in range(N - 1):
      x = p[j]
      y = p[j + 1]
      if x > y: x, y = y, x
      
      if el[k] == (x, y):
        table[i][k] = 1
        break
revtable = [0] * (N - 1)
for i in range(N - 1):
  for j in range(M):
    if table[j][i]: revtable[i] += pow(2, j)

dp = [0] * pow(2, M)
dp[0] = 1


for i in range(N - 1):
  for j in range(pow(2, M) - 1, -1, -1):
    dp[revtable[i] | j] += dp[j]
print(dp[-1])

Solution (Python):




n = int(input())
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append((b, i))
    adj[b].append((a, i))
m = int(input())
ranges = [tuple(map(int, input().split())) for i in range(m)]



def findpath(u, v, parent=None):
    """uからvへの経路 (辺の集合)"""
    if u == v:
        return set()
    for x, i in adj[u]:
        if x == parent:
            continue
        p = findpath(x, v, u)
        if p is not None:
            p.add(i)  
            return p
    return None

def powerset(seq, bag):
    """[(seqの部分集合s, bag[e] for e in s の和集合)]"""
    if len(seq) <= 1:
        yield ((seq[0],), bag[seq[0]])
        yield ((), set())
    else:
        for s, b in powerset(seq[1:], bag):
            yield ((seq[0],) + s, b | bag[seq[0]])
            yield (s, b)



paths = [findpath(u, v) for u, v in ranges]


white = 0
for s, b in powerset(list(range(m)), paths):
    l = len(s)
    if l <= 0:
        continue
    
    w = 2 ** (n - 1 - len(b))
    
    sign = -1 if l % 2 == 0 else 1    
    white += sign * w


coloring = 2 ** (n - 1) - white
print(coloring)

Solution (Python):




n = int(input())
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
m = int(input())
ranges = []
for i in range(m):
    u, v = map(int, input().split())
    ranges.append((u, v))



def normalized(u, v):
    return (min(u, v), max(u, v))

def findpath(u, v, visited=None):
    """uからvへの経路 (辺の集合)"""
    if visited is None:
        visited = set()
    if u == v:
        return set()
    if u in visited:
        return None
    visited.add(u)
    for x in adj[u]:
        p = findpath(x, v, visited)
        if p is not None:
            p.add(normalized(u, x))
            return p

def powerset(seq, bag):
    """(seqの部分集合s, bag[e] for e in s の和集合)"""
    if len(seq) <= 1:
        yield ((seq[0],), bag[seq[0]])
        yield ((), set())
    else:
        for s, b in powerset(seq[1:], bag):
            yield ((seq[0],) + s, b | bag[seq[0]])
            yield (s, b)



paths = {}
for u, v in ranges:
    paths[(u, v)] = findpath(u, v)


coloring = 0
for s, b in powerset(ranges, paths):
    l = len(s)
    if l <= 0:
        continue
    
    c = 2 ** ((n - 1) - len(b))
    
    sign = -1 if l % 2 == 0 else 1    
    coloring += sign * c


coloring = 2 ** (n - 1) - coloring
print(coloring)

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

import numpy as np

MOD = 10 ** 9 +7

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

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

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

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

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

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

n_edges = popcnt(s)

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

Solution (Python):
import sys
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)
        if a > b:
            a, b = b, a
        edges.append((a, b))
    M = int(input())
    uvs = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

    def getPath(vSt, vEn):
        def dfs(vNow, vPar):
            if vNow == vEn:
                path.append(vNow)
                return True
            for v2 in adjL[vNow]:
                if v2 != vPar:
                    if dfs(v2, vNow):
                        path.append(vNow)
                        return True
        path = []
        dfs(vSt, -1)
        return path

    edgeConstraints = []
    for u, v in uvs:
        path = getPath(u, v)
        setEdge = set()
        for j in range(len(path)-1):
            a, b = path[j], path[j+1]
            if a > b:
                a, b = b, a
            setEdge.add((a, b))
        edge = 0
        for j, (a, b) in enumerate(edges):
            if (a, b) in setEdge:
                edge |= 1<<j
        edgeConstraints.append(edge)

    numEs = []
    for S in range(1<<M):
        edge = 0
        for i, edgeConstraint in enumerate(edgeConstraints):
            if (S>>i) & 1:
                edge |= edgeConstraint
        numE = bin(edge).count('1')
        numEs.append(numE)

    pow2s = [1]
    for i in range(N):
        pow2s.append(pow2s[-1]*2)

    ans = 0
    for S, numE in enumerate(numEs[1:], 1):
        num1 = bin(S).count('1')
        if num1 % 2:
            ans += pow2s[N-1-numE]
        else:
            ans -= pow2s[N-1-numE]

    print(pow2s[N-1] - ans)


solve()

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

N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


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

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    RET=0
    ANS=[y]
    while y!=x:
        RET+=1<<DICT[tuple(sorted([y,USE[y]]))]
        y=USE[y]

    return RET

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

for i in range(N-1):
    B=0
    for k in range(M):
        if 1<<i & Q2[k]!=0:
            B+=1<<k
        
    for j in range((1<<M)-1,-1,-1):
        DP[j|B]+=DP[j]

print(DP[-1])

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

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

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
    
graph = [[] for _ in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
  
def make_tree(graph, root) -> (list, list):
  INF = 10 ** 15
  dist = [INF] * len(graph)
  parent = [-1] * len(graph)
  stack = [root]
  dist[root] = 0
  parent[root] = root
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if dist[g] > dist[s] + 1:
        dist[g] = dist[s] + 1
        parent[g] = s
        stack.append(g)
  return dist, parent
 
def lca(u, v, dist, parent):
  distu, distv = dist[u], dist[v]
  if distu > distv:
    for _ in range(distu - distv):
      u = parent[u]
  if distv > distu:
    for _ in range(distv - distu):
      v = parent[v]
  while u != v:
    u, v = parent[u], parent[v]
  return u

dist, parent = make_tree(graph, 1)

tree_lca = []
for i in range(M):
    tmp = 0
    u, v = UV[i]
    l = lca(u, v, dist, parent)
    while u != l:
        tmp |= 1 << u
        u = parent[u]
    while v != l:
        tmp |= 1 << v
        v = parent[v]
    tree_lca.append(tmp)

answer = 2 ** (N - 1)
for i in range(1, 2 ** M):
    tmp = 0
    for j in range(M):
        if (i >> j) & 1:
            tmp |= tree_lca[j]
    cnt = popcnt(tmp)

    if popcnt(i) % 2 == 1:
        answer -= 2 ** (N - 1 - cnt) 
    else:
        answer += 2 ** (N - 1 - cnt) 
        
print(answer)

Solution (Python):
from collections import deque
n = int(input())
ls = [list(map(lambda x:int(x)-1, input().split())) for i in range(n-1)]
m = int(input())
cond = [list(map(lambda x:int(x)-1, input().split())) for i in range(m)]
ans=0
graph = [[0]*(n) for _ in range(n)]



for i in range(n-1):
    graph[ls[i][0]][ls[i][1]]+=1<<i
    graph[ls[i][1]][ls[i][0]]+=1<<i

eset = []

for cns in cond:
    d=deque()
    d.append([cns[0], 0])
    while d:
        s, es = d.pop()
        for i in range(n):
            if graph[s][i] and not es&graph[s][i]:
                es2 = es|graph[s][i]
                if i == cns[1]:
                    eset.append(es2)
                    break
                d.append([i, es2])

for i in range(1<<m):
    mask=0
    for j in range(m):
        if i&1<<j:
            mask|=eset[j]
    white=bin(mask).count('1')
    if bin(i).count('1')%2:
        ans-=1<<(n-1-white)
    else:
        ans+=1<<(n-1-white)

print(ans)

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

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


def get_path(u, v):
    stack = [u]
    prev = [None] * (N+1)
    visited = [False] * (N+1)
    visited[u] = True
    while stack:
        node = stack.pop()
        for next, i in G[node]:
            if not visited[next]:
                visited[next] = True
                prev[next] = (node, i)
                stack.append(next)
    path = 0
    node = v
    while node != u:
        p, i = prev[node]
        node = p
        path += 1 << i
    return path


def count(bits, N):
    cnt = 0
    for i in range(N):
        if ((bits >> i) & 1) == 1:
            cnt += 1
    return cnt


M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]
paths = [get_path(u, v) for u, v in uv]
ans = 2**(N-1)
for bit in range(1, 1 << M):
    cnt = 0
    tmp = 0
    for i in range(M):
        if ((bit >> i) & 1) == 1:
            cnt += 1
            tmp |= paths[i]
    ans += (-1)**cnt * 2**(N-1-count(tmp, N-1))
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def popcount(i):
    return bin(i).count('1')

def dfs(i, N, nodes, src, dest):
    """ DFS(木、再帰、重みなし) """

    dist = [INF] * N
    def rec(u, prev, c):
        if u == dest:
            return True
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                if rec(v, u, c+1):
                    
                    A[i] |= 1 << edges[(u, v)]
                    return True
        return False
    rec(src, -1, 0)

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = i
    edges[(b, a)] = i

M = INT()

A = [0] * M
for i in range(M):
    u, v = MAP()
    u -= 1; v -= 1
    dfs(i, N, nodes, u, v)


ans = 2 ** (N-1)
for S in range(1, 1<<M):
    
    S2 = 0
    for i in range(M):
        if S & 1<<i:
            S2 |= A[i]
    
    edgecnt = popcount(S2)
    
    cnt = 2**(N-1-edgecnt)
    if popcount(S) % 2 == 1:
        ans -= cnt
    else:
        ans += cnt
print(ans)

Solution (Python):
N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


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

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    ANS=[y]
    while y!=x:
        y=USE[y]
        ANS.append(y)

    RET=[]

    for i in range(1,len(ANS)):
        RET.append(DICT[tuple(sorted([ANS[i-1],ANS[i]]))])

    return set(RET)

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

for i in range(N-1):
    B=0
    for k in range(M):
        if i in Q2[k]:
            B+=1<<k
        
    for j in range((1<<M)-1,-1,-1):
        DP[j|B]+=DP[j]

print(DP[-1])