Problem:
 Score : 600 points    Problem Statement  We have a tree with N vertices numbered 1 to N .
The i -th edge in this tree connects Vertex a_i and Vertex b_i . Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?   The i -th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i , which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.       Constraints   2 \leq N \leq 50  1 \leq a_i,b_i \leq N  The graph given in input is a tree.  1 \leq M \leq \min(20,\frac{N(N-1)}{2})  1 \leq u_i < v_i \leq N  If i \not= j , either u_i \not=u_j or v_i\not=v_j  All values in input are integers.         Input  Input is given from Standard Input in the following format:  N  a_1  b_1  :  a_{N-1}  b_{N-1}  M  u_1  v_1  :  u_M  v_M       Output  Print the number of ways to paint the edges that satisfy all of the M conditions.        Sample Input 1 3
1 2
2 3
1
1 3      Sample Output 1 3  The tree in this input is shown below:     All of the M restrictions will be satisfied if Edge 1 and 2 are respectively painted (white, black), (black, white), or (black, black), so the answer is 3 .       Sample Input 2 2
1 2
1
1 2      Sample Output 2 1  The tree in this input is shown below:     All of the M restrictions will be satisfied only if Edge 1 is painted black, so the answer is 1 .       Sample Input 3 5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5      Sample Output 3 9  The tree in this input is shown below:           Sample Input 4 8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8      Sample Output 4 62  The tree in this input is shown below:

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007




import sys
readline = sys.stdin.readline



n = I()
G = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = LI()
    G[u - 1] += [(i, v - 1)]
    G[v - 1] += [(i, u - 1)]


def dfs(root):
    q = [root]
    path_bit = [-1] * n
    path_bit[root] = 0
    while q:
        u = q.pop()
        for i, v in G[u]:
            if path_bit[v] != -1:
                continue
            path_bit[v] = path_bit[u] | 1 << i
            q += [v]
    return path_bit



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


m = I()
cond = LIR(m)
path_bit = dfs(0)
cond_bit = [0] * m
for j, (u, v) in enumerate(cond):
    cond_bit[j] = path_bit[u - 1] ^ path_bit[v - 1]

L = [0] * (2 ** m)
C = [0] * n
for i in range(2 ** m):
    if i != 0:
        L[i] = L[(i ^ (i & -i))] | cond_bit[(i & -i).bit_length() - 1]


    cond_cnt = popcnt(i)

    if cond_cnt % 2:
        C[n - 1 - popcnt(L[i])] -= 1
    else:
        C[n - 1 - popcnt(L[i])] += 1


ans = 0
for i in range(n):
    ans += 2 ** i * C[i]


print(ans)

Solution (Python):






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

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

def func(x, g, p):
    
    if len(e[x]) == 1 and p != -1:
        return -1
    for edge in e[x]:
        if edge[0] == p:
            continue
        elif edge[0] == g:
            
            return 1 << edge[1]
        temp = func(edge[0], g, x)
        
        if temp >= 0:
            
            return temp + (1 << edge[1])
    return -1

p = []
for u, v in uv:
    p.append(func(u, v, -1))


flag = -1
ans = 2 ** (n-1)

base = 2 ** (n-1)
for i in range(1, 1 << m):
    temp = list(reversed(list(str(bin(i)))[2:]))
    c = 0
    
    for j, x in enumerate(temp):
        if x == '1':
            c = c | p[j]
    
    hoge = str(bin(base + c)).count('0') - 1
    if temp.count('1') % 2 == 0:
        flag = 1
    else:
       flag = -1
    ans += flag * (2 ** hoge)
    
print(ans)

Solution (Python):
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
edge = [0 for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        edge[y] = edge[x] + 2**(y-1)
        seen[y] = 1
        now.append(y)

def count1(x):
  y = bin(x)
  z = 0
  l = len(y)
  for li in range(l):
    if y[li] == '1':
      z += 1
  return z

def count2(x):
  z = 0
  l = len(x)
  for li in range(l):
    if x[li] == '1':
      z += 1
  return z


m = int(input())
restr = []
for _ in range(m):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  restr.append(edge[u]^edge[v])



ans = 0
for i in range(2**m):
  b = bin(i)[2:]
  time = '0' * (m-len(b)) + b
  tmp = 0
  for j in range(m):
    if time[j] == '1':
      tmp |= restr[j]
  if count2(time) % 2 == 0:
    ans += 2**(n-1-count1(tmp))
    
  else:
    ans -= 2**(n-1-count1(tmp))
    

print(ans)

Solution (Python):
N = int(input())
E = [[int(l) for l in input().split()] for _ in range(N-1)]
M = int(input())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

C = [0]*M
for i in range(N-1):
    uf = UnionFind(N)
    for e in E:
        if e == E[i]:
            continue
        uf.unite(e[0], e[1])
    for l in range(M):
        if uf.isSameGroup(L[l][0], L[l][1]):
            continue
        C[l] |= 1 << i

import itertools

ans = 0
L = [int(i) for i in range(M)]
for m in range(M+1):
    for P in itertools.combinations(L, m):
        white = 0
        for j in P:
            white |= C[j]
        if m%2:
            ans -= 1 << N-1-bin(white).count("1")
        else:
            ans += 1 << N-1-bin(white).count("1")
print(ans)

Solution (Python):
N = int(input())
ab = [[] for _ in range(N)]
for i in range(N-1) :
  a, b = map(int, input().split())
  ab[a-1].append((b-1, i))
  ab[b-1].append((a-1, i))
M = int(input())
uv = [[int(i) for i in input().split()] for _ in range(M)]

dp = [0] * M
def dfs(cur, pre, t, i) :
  if cur == t : return True
  for nex, j in ab[cur] :
    if nex == pre : continue
    if dfs(nex, cur, t, i) :
      dp[i] |= 1<<j
      return True
  return False

for i, (u, v) in enumerate(uv) :
  dfs(u-1, -1, v-1, i)

ret = 1<<(N-1)
for i in range(1, 1<<M) :
  sgn = 1
  s = 0
  for j in range(M) :
    if i & (1<<j) :
      s |= dp[j]
      sgn *= -1
  ret += sgn * (1<<(N-1-bin(s).count('1')))

print(ret)

Solution (Python):
n = int(input())
g = [[] for _ in range(n)]
e = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
    e.append((a - 1, b - 1))
m = int(input())
l = [set() for _ in range(m)]
for i in range(m):
    u, v = map(int, input().split())
    s = [u - 1]
    dist = [-1] * n
    dist[u - 1] = 0
    r = [-1] * n
    while s:
        d = s.pop()
        for node in g[d]:
            if dist[node] == -1:
                s.append(node)
                dist[node] = dist[d] + 1
                r[node] = d
    d = v - 1
    while r[d] != -1:
        a, b = min(d, r[d]), max(d, r[d])
        l[i].add(e.index((a, b)))
        d = r[d]
ans = 0
for i in range(2 ** m):
    cnt = 0
    s = set()
    for j in range(m):
        if (i >> j) & 1:
            cnt += 1
            s |= l[j]
    if cnt % 2:
        ans -= 2 ** (n - len(s) - 1)
    else:
        ans += 2 ** (n - len(s) - 1)
print(ans)

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


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

def main():
    n = int(input())
    edge = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    m = int(input())
    dg = 100
    uv = []
    for _ in [0]*m:
        u,v = map(int,input().split())
        uv.append(u*dg-dg+v-1)

    
    par = [-2]*n
    root = 0
    par[0] = -1

    tank = [0]
    order = []
    orderIdx = [0]*n
    cnt = 0
    while tank:
        now = tank.pop()
        for nxt in edge[now]:
            if par[nxt] == -2:
                par[nxt] = now
                tank.append(nxt)
        order.append(now)
        orderIdx[now] = cnt
        cnt += 1
    
    res = pow(2,n-1)
    
    bitOne = set()
    for i in range(m):
        bitOne.add(1<<i)

    
    dp = [0]*(1<<m)
    for i in range(1,1<<m):
        pc = popcnt(i)
        if pc == 1:
            
            idx = (-i&i).bit_length()-1
            
            u,v = uv[idx]//dg,uv[idx]%dg

            
            
            tmp = 0
            while u != v:
                if orderIdx[u] < orderIdx[v]:
                    tmp |= (1<<v)
                    v = par[v]
                else:
                    tmp |= (1<<u)
                    u = par[u]
            dp[i] = tmp
        
        else:
            dp[i] = dp[(-i)&i] | dp[((-i)&i)^i]
    
        res += (-1)**(pc%2)*pow(2,n-1-popcnt(dp[i]))

    print(res)

if __name__ == '__main__':
    main()

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


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

def main():
    n = int(input())
    edge = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    m = int(input())
    dg = 100
    uv = []
    for _ in [0]*m:
        u,v = map(int,input().split())
        uv.append(u*dg-dg+v-1)

    
    par = [-2]*n
    root = 0
    par[0] = -1

    tank = [0]
    order = []
    orderIdx = [0]*n
    cnt = 0
    while tank:
        now = tank.pop()
        for nxt in edge[now]:
            if par[nxt] == -2:
                par[nxt] = now
                tank.append(nxt)
        order.append(now)
        orderIdx[now] = cnt
        cnt += 1
    
    res = pow(2,n-1)
    
    bitOne = set()
    for i in range(m):
        bitOne.add(1<<i)

    
    dp = [0]*(1<<m)
    for i in range(1,1<<m):
        pc = popcnt(i)
        if pc == 1:
            
            idx = (-i&i).bit_length()-1
            
            u,v = uv[idx]//dg,uv[idx]%dg

            
            
            tmp = 0
            while u != v:
                if orderIdx[u] < orderIdx[v]:
                    tmp |= (1<<v)
                    v = par[v]
                else:
                    tmp |= (1<<u)
                    u = par[u]
            dp[i] = tmp
        
        else:
            dp[i] = dp[(-i)&i] | dp[((-i)&i)^i]
    
        res += (-1)**(pc%2)*pow(2,n-1-popcnt(dp[i]))

    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
from subprocess import *
cmd=['pypy3','-c',"""
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
    edges[(min(a[i],b[i]),max(a[i],b[i]))]=i
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[0 for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i]+=2**edges[(s,t)]
        x=parents[x]
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
q=deque([])
q.append(0)
S=[0 for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|root[j]
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-bin(S[i]).count("1")-1)
print(ans)
"""]
call(cmd)

Solution (Python):


import sys
readline = sys.stdin.readline

import numpy as np

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]


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


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]

n_edges = popcnt(S)
x = 1 << (N - 1 - n_edges)
answer = (x * sgn).sum()
print(answer)

Solution (Python):


import sys
readline = sys.stdin.readline

import numpy as np

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]


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


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]

n_edges = popcnt(S)

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

Solution (Python):


import sys
readline = sys.stdin.readline

import numpy as np

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]


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


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]

n_edges = popcnt(S)

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

Solution (Python):


import numpy as np
import sys
readline = sys.stdin.readline

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

M = int(readline())


def get_path(U, V):
    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 = []
for i in range(M):
    u, v = map(int, readline().split())
    condition_path.append(get_path(u, v))


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


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]


n_edges = popcnt(S)
x = 1 << (N - 1 - n_edges)
answer = np.sum(x * sgn)
print(answer)

Solution (Python):


import numpy as np
import sys
readline = sys.stdin.readline

N = int(readline())
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, readline().split())
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

M = int(readline())


def get_path(U, V):
    visited = 0
    q = [(U, 0)]
    while q:
        v, used = q.pop()
        if v == V:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


condition_path = []
for i in range(M):
    u, v = map(int, readline().split())
    condition_path.append(get_path(u, v))


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


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]


n_edges = popcnt(S)
x = 1 << (N - 1 - n_edges)
answer = np.sum(x * sgn)
print(answer)

Solution (Python):
from collections import defaultdict


def dfs(s, t):
    visited = 0
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    conditions.append(dfs(u, v))

link_conditions = [int(''.join(b), 2) for b in zip(*map(('{:0' + str(n - 1) + 'b}').format, conditions))]

dp = defaultdict(int)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print(dp[(1 << m) - 1])

Solution (Python):
from collections import defaultdict


def dfs(s, t):
    visited = 0
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    conditions.append(dfs(u, v))

link_conditions = [int(''.join(i), 2) for i in zip(*[bin(j)[2:].zfill(n - 1) for j in conditions])]

dp = defaultdict(int)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print(dp[(1 << m) - 1])

Solution (Python):
from collections import defaultdict


def dfs(s, t):
    visited = 0
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    conditions.append(dfs(u, v))

link_conditions = [int(''.join(b), 2) for b in zip(*map(('{:0' + str(n - 1) + 'b}').format, conditions))]

dp = defaultdict(lambda: 0)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print(dp[(1 << m) - 1])

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

es = [[] for i in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))

paths = [0] * M
for i,(u,v) in enumerate(UV):
    u,v = u-1,v-1
    stack = [u]
    visited = [0] * N
    visited[u] = 1
    edges = [-1] * N
    while stack:
        s = stack.pop()
        for to,j in es[s]:
            if visited[to]: continue
            visited[to] = 1
            edges[to] = j
            stack.append(to)
            if to == v:
                break
        else:
            continue
        while edges[v] >= 0:
            j = edges[v]
            paths[i] |= (1<<j)
            a,b = AB[j]
            a,b = a-1,b-1
            v = a if a!=v else b
        break

dp = [0] * (1<<M)
for b in range(1,1<<M):
    k = len(bin(b))-3
    dp[b] = dp[b-2**k] | paths[k]

ans = 0
for i,d in enumerate(dp):
    b = N-1 - bin(d).count('1')
    ans += 2**b if bin(i).count('1')%2==0 else -2**b
print(ans)

Solution (Python):


N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
DE = [0] * N
Q = [0]
while Q:
    i = Q.pop()
    for a in X[i][::-1]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] + 1
            X[a].remove(i)
            Q.append(a)

def lp(u, v):
    t = 0
    while u != v:
        if DE[u] > DE[v]:
            t += 1 << u-1
            u = P[u]
        elif DE[u] < DE[v]:
            t += 1 << v-1
            v = P[v]
        else:
            t += 1 << u-1
            t += 1 << v-1
            u = P[u]
            v = P[v]
    
    return t

Y = []
M = int(input())
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    Y.append(lp(a, b))

def popcnt(n):
    return bin(n).count("1")

D = {1<<i: i for i in range(50)}
Z = [0] * (1<<M)
ans = 0
CC = [0] * N
for m in range(1<<M):
    a = m & (-m)
    if a == m:
        if a == 0:
            Z[m] = 0
        else:
            Z[m] = Y[D[a]]
    else:
        Z[m] = Z[m^a] | Y[D[a]]
    
    CC[N - 1 - popcnt(Z[m])] += (1 if popcnt(m) & 1 == 0 else -1)

print(sum([2 ** i * CC[i] for i in range(N)]))

Solution (Python):
from collections import defaultdict


def dfs(s, t, links):
    visited = set()
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited.add(v)
        for lb, u in links[v]:
            if u in visited:
                continue
            q.append((u, used | lb))


n = int(input())
links = [set() for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    lb = 1 << i
    links[a].add((lb, b))
    links[b].add((lb, a))
conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    conditions.append(dfs(u, v, links))

link_conditions = [int(''.join(b), 2) for b in zip(*map(('{:0' + str(n - 1) + 'b}').format, conditions))]

dp = defaultdict(lambda: 0)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print(dp[(1 << m) - 1])

Solution (Python):
def dfs(s, t, links):
    visited = set()
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited.add(v)
        for lb, u in links[v]:
            if u in visited:
                continue
            q.append((u, used | lb))


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


n = int(input())
links = [set() for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    lb = 1 << i
    links[a].add((lb, b))
    links[b].add((lb, a))
conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    conditions.append(dfs(u, v, links))

ans = 0
for i in range(1 << m):
    cnd_cnt = bitcount32(i)
    bit = 0
    k = i
    while k:
        b = k & -k
        j = b.bit_length() - 1
        bit |= conditions[j]
        k ^= b
    free_link_cnt = n - 1 - bitcount32(bit)
    val = 2 ** free_link_cnt
    if cnd_cnt % 2:
        ans -= val
    else:
        ans += val
print(ans)

Solution (Python):
from collections import deque
from collections import Counter
N=int(input())
E=[set() for _ in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    E[a].add((b,i))
    E[b].add((a,i))
M=int(input())
P=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

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

def bfs(S,G,p):
    q=deque([S])
    parent=[(-1,-1)]*N
    while q:
        n=q.popleft()
        for to,i in E[n]:
            if parent[to][0]!=-1:
                continue
            parent[to]=(n,i)
            if to==G:
                break
            q.append(to)
    n=G
    while n!=S:
        n,i=parent[n]
        pc[p].add(i)

for i,p in enumerate(P):
    bfs(p[0],p[1],i)

ans=0
for i in range(1<<M):
    whiteset=set()
    sign=1
    for j in range(M):
        if i>>j&1:
            whiteset|=pc[j]
            sign*=-1
    ans+=sign*(1<<(N-1-len(whiteset)))

print(ans)