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):
def dfs(tree, v, tv, p, es):
    if v == tv:
        return True
    for e in tree[v]:
        if e[0] == p:
            continue
        if dfs(tree, e[0], tv, v, es):
            es.append(e[1])
            return True
    return False

def main():
    n = int(input())
    tree = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append((b, i))
        tree[b].append((a, i))
    m = int(input())
    eset = [0]*m
    for i in range(m):
        u, v = map(int, input().split())
        es = []
        dfs(tree, u-1, v-1, -1, es)
        for e in es:
            eset[i] |= 1 << e

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


main()

Solution (Python):
def main():
  import sys
  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 -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
  
  
  EG = []
  def dfs(u,v,p):
    if u == v:
      return True
    for t,i in E[u]:
      if t == p:
        continue
      if dfs(t,v,u):
        EG.append(i)
        return True
    return False
  
  M = int(input())
  EM = []
  for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    EM.append((u,v))

  
  ES = []
  for i in range(M):
    u,v = EM[i]
    EG = []
    dfs(u,v,-1)
    ES.append((u,v,EG))
  
  ans = 0
  for i in range(1<<M):
    
    
    EG2 = []
    bc = 0
    for j in range(M):
      if (i>>j)&1 == 1:
        bc += 1
        EG2 += ES[j][2]
    p = len(set(EG2))
    
    if bc%2 == 0:
      ans += 2**(N-1-p)
    else:
      ans -= 2**(N-1-p)
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
def main():
  import sys
  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 -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
  
  EG = []
  def dfs(u,v,p):
    if u == v:
      return True
    for t,i in E[u]:
      if t == p:
        continue
      if dfs(t,v,u):
        EG.append(i)
        return True
    return False
  
  M = int(input())
  EM = []
  for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    EM.append((u,v))
  
  ES = []
  for i in range(M):
    u,v = EM[i]
    EG = []
    dfs(u,v,-1)
    ES.append((u,v,EG))
  
  ans = 0
  for i in range(1<<M):
    EG2 = []
    bc = 0
    for j in range(M):
      if (i>>j)&1 == 1:
        bc += 1
        EG2 += ES[j][2]
    p = len(set(EG2))
    if bc%2 == 0:
      ans += 2**(N-1-p)
    else:
      ans -= 2**(N-1-p)
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
def dfs(tree, v, tv, p, es):
    if v == tv:
        return True
    for e in tree[v]:
        if e[0] == p:
            continue
        if dfs(tree, e[0], tv, v, es):
            es.append(e[1])
            return True
    return False


def main():
    n = int(input())
    tree = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append((b, i))
        tree[b].append((a, i))
    m = int(input())
    eset = [0]*m
    for i in range(m):
        u, v = map(int, input().split())
        es = []
        dfs(tree, u-1, v-1, -1, es)
        for e in es:
            eset[i] |= 1 << e

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


main()

Solution (Python):
n = int(input())
adj = [[] for _ in range(n)]
adj_dict = dict()

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



from itertools import product

N = I()
a,b = Line(N-1,2)
M = I()
u,v = Line(M,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt


def shortest_path(pt,s,t):
    n = len(pt)
    used = [False]*n
    pre = [-1]*n
    q = [s]
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if not used[j]:
                    used[j] = True
                    pre[j] = i
                    q1.append(j)
        q = q1

    if used[t]:
        path = [t]
        p = t
        while True:
            p = pre[p]
            path.append(p)
            if p == s:
                break
        return list(reversed(path))
    else:
        return []

d = defaultdict(int)
count = 0
for i in range(N-1):
    x,y = min(a[i]-1,b[i]-1),max(a[i]-1,b[i]-1) 
    if not d[(x,y)]:
        d[(x,y)] = count
        d[(y,x)] = count
        count += 1

pt = edges_to_pt(a,b,N)
h_index = [[] for _ in range(M)]
for i in range(M):
    p = shortest_path(pt,u[i]-1,v[i]-1)
    for j in range(len(p)-1):
        x,y = p[j],p[j+1]
        h_index[i].append(d[(x,y)])

bit_h = [0]*M
for i in range(M):
    bits = 0
    for h in h_index[i]:
        bits += 2**h
    bit_h[i] = bits

ans_r = 0
A = list(product([0,1],repeat=M))
for a in A[1:]:
    bits = 0
    edge_num = 0
    for i in range(M):
        if a[i]:
            bits |= bit_h[i]
            edge_num += 1
    one_count = 0
    for i in range(count+1):
        if bits>>i&1:
            one_count += 1
    ans_r += (-1)**(edge_num-1)*2**(N-1-one_count)

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

Solution (Python):
from collections import deque

def bfs():
    q = deque([0])
    bit = [-1]*N
    bit[0] = 0
    serial = 0
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if bit[nv]!=-1:
                continue
            bit[nv] = bit[v]|(1<<serial)
            serial += 1
            q.append(nv)
    
    return bit

N = int(input())
adj_list = [[] for _ in range(N)]

for _ in range(N-1):
    ai, bi = map(int, input().split())
    adj_list[ai-1].append(bi-1)
    adj_list[bi-1].append(ai-1)

bit = bfs()
M = int(input())
uv = []
path_bit = []

for _ in range(M):
    ui, vi = map(int, input().split())
    uv.append((ui-1, vi-1))
    path_bit.append(bit[ui-1]^bit[vi-1])

houzyo = 0

for i in range(1, 2**M):
    covered = 0
    c = 0
    
    for j in range(M):
        if (i>>j)&1:
            covered |= path_bit[j]
            c += 1
    
    no_covered = 0
    
    for j in range(N-1):
        if not (covered>>j)&1:
            no_covered += 1
    
    if c%2==1:
        houzyo += 2**no_covered
    else:
        houzyo -= 2**no_covered

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

Solution (Python):
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
M = int(input())
UV = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

P = [-1]*N
P[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if P[j]!=-1: continue
        P[j] = i
        q.append(j)
P[0] = -1

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

path = []
for u,v in UV:
    u -= 1
    v -= 1
    tmp = []
    d = dist_bfs(N,E,u)
    q = [v]
    while q:
        i = q.pop()
        di = d[i]
        for j in E[i]:
            if d[j] == di-1:
                q.append(j)
                if P[i]==j:
                    tmp.append(i)
                else:
                    tmp.append(j)
    path.append(set(tmp))

ans = 2**(N-1)
for i in range(1,2**M):
    tmp = set(range(1,N))
    cnt = 0
    for j in range(M):
        if (i>>j)&1==0:continue
        cnt += 1
        tmp -= path[j]
    ans += ((-1)**cnt) * (2**(len(tmp)))
print(ans)

Solution (Python):

"""
20個しかないので包除原理？
使う、使わないで 2**20通り

答え = 2**N - 1満たさない + 2つ満たさない - 3つ満たさない…
で表される

各場合はいずれかのパスに属す点以外は自由に塗れる
各パス上の点をbitで管理
黒に塗ってはいけない点のかずをあぶりだす

計算量は 2**20

"""
from collections import deque

N = int(input())

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1
    c = N+i

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []
    dic[c] = []

    dic[a].append(c)
    dic[b].append(c)
    dic[c].append(a)
    dic[c].append(b)

M = int(input())
bitlis = []

for loop in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1
    
    bits = [0] * N + [2**i for i in range(N-1)]
    dis = [float("inf")] * (2*N-1)
    dis[u] = 0

    q = deque([u])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:
            if dis[nex] > dis[now] + 1:
                dis[nex] = dis[now] + 1
                bits[nex] += bits[now]
                q.append(nex)

    bitlis.append(bits[v])


uselis = [0] * (M+1)

for use in range(2**M):

    white = 0
    usenum = 0
    for i in range(M):
        if use & (2**i) > 0:
            white |= bitlis[i]
            usenum += 1

    able = N-1
    ws = format(white,"b")
    for i in ws:
        if i == "1":
            able -= 1

    uselis[usenum] += 2 ** able


ans = 2 ** (N-1)

for i in range(M):

    i += 1

    if i % 2 == 1:
        ans -= uselis[i]
    else:
        ans += uselis[i]

print (ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,g,p):
    global tmp
    if s == g:
        tmp = []
        return True
    for (v,i) in edge[s]:
        if v == p:
            continue
        if dfs(v,g,s):
            tmp.append(i)
            return True
    return False

n = I()
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    edge[a].append((b,i))
    edge[b].append((a,i))

m = I()
lst = []
tmp = []
for _ in range(m):
    u,v = LI()
    u -= 1
    v -= 1
    dfs(u,v,-1)
    lst.append(tmp)

"""m個の制約がどの辺を通るかbitで管理"""
e = [0]*m
for i in range(m):
    x = 0
    for j in lst[i]:
        x |= 1<<j
    e[i] = x

"""包除原理"""
ans = 0
for i in range(1<<m):
    black = 0 
    cnt = 0 
    """どの制約を使うか"""
    for j in range(m):
        if i>>j & 1:
            cnt += 1
            black |= e[j]

    cnt2 = 0 
    for j in range(n-1):
        if black >> j & 1:
            cnt2 += 1
    if cnt % 2: 
        ans -= 1<<(n-1-cnt2) 
    else:
        ans += 1<<(n-1-cnt2) 
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n 
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

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

passing=[] 
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
Cond=[0]*(2**m)

for i in range(1,2**m):
  i_ct=popcount(i)
  Cond[i]=Cond[i^(i&(-i))]|passing[len(bin(i&(-i)))-3]
  cond_ct=popcount(Cond[i]) 

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n-1)]
m = I()
uv = [LI() for _ in range(m)]

edge = [[] for i in range(n)]
lst = [[None]*n for i in range(n)]
cnt = 0
for i,[a,b] in enumerate(ab):
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    lst[a-1][b-1] = i
    lst[b-1][a-1] = i

L = []
for u,v in uv:
    stack = deque()
    stack.append(u-1)
    flg = [True]*n
    par = [None]*n
    par[u-1] = -1
    while stack:
        x = stack.pop()
        if x == v-1:
            break
        flg[x] = False
        for y in edge[x]:
            if flg[y]:
                par[y] = x
                stack.append(y)
    tmp = v-1
    tmp2 = []
    while 1:
        if par[tmp] == -1:
            break
        tmp2.append(lst[tmp][par[tmp]])
        tmp = par[tmp]
    tmp2.sort()
    L.append(tmp2)

e = [0]*m
for i in range(m):
    x = 0
    for j in L[i]:
        x |= 1<<j
    e[i] = x

ans = 0
for i in range(1<<m):
    black = 0
    cnt = 0
    for j in range(m):
        if (i>>j & 1):
            cnt += 1
            black |= e[j]
    cnt2 = 0
    for j in range(n-1):
        if (black>>j & 1):
            cnt2 += 1
    if cnt % 2:
        ans -= 1<<(n-1-cnt2)
    else:
        ans += 1<<(n-1-cnt2)
print(ans)

Solution (Python):
import collections
from itertools import combinations
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)]


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


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0
for i in range(1, 2**M):
    tmp = 2**(N-1) - 1
    for j in range(M):
        if (i >> j) % 2 == 1:
            u, v = uv[j]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
    ans2 += ((-1)**(popcount(i)-1)) * (1 << popcount(tmp))
    
print(ans-ans2)

Solution (Python):
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





class DoublingLCA:
    """
    LCA ダブリング版
    初期化 O(NlogN)、クエリ O(logN)
    """

    def __init__(self, graph, max_v, root):
        """
        :param list of (list of int) graph:
        :param int max_v:
        :param int root:
        """
        self.graph = graph
        self.size = max_v + 1
        self.root = root

        
        self.MAX_LOG_V = math.floor(math.log(self.size, 2)) + 1
        
        self.depths = [-1] * self.size
        
        self.parents = [[-1] * self.size for _ in range(self.MAX_LOG_V)]

        self._init()

    def _init(self):
        
        seen = [False] * self.size
        stack = [(self.root, 0, -1)]
        while stack:
            v, d, par = stack.pop()
            self.parents[0][v] = par
            self.depths[v] = d
            seen[v] = True
            for u in self.graph[v]:
                if not seen[u]:
                    stack.append((u, d + 1, v))

        
        for k in range(self.MAX_LOG_V - 1):
            for v in range(self.size):
                if self.parents[k][v] < 0:
                    
                    self.parents[k + 1][v] = -1
                else:
                    self.parents[k + 1][v] = self.parents[k][self.parents[k][v]]

    def lca(self, u, v):
        """
        :param int u:
        :param int v:
        """
        
        if self.depths[u] > self.depths[v]:
            u, v = v, u
        for k in range(self.MAX_LOG_V):
            if (self.depths[v] - self.depths[u]) >> k & 1:
                v = self.parents[k][v]
        if v == u:
            return v

        
        for k in reversed(range(self.MAX_LOG_V)):
            if self.parents[k][u] != self.parents[k][v]:
                u = self.parents[k][u]
                v = self.parents[k][v]
        return self.parents[0][u]

    def distance(self, u, v):
        """
        u, v 間の距離
        depth[u] + depth[v] - depth[lca] * 2
        :param u:
        :param v:
        :rtype: int
        """
        lca = self.lca(u, v)
        return self.depths[u] + self.depths[v] - self.depths[lca] * 2




N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
M = int(sys.stdin.buffer.readline())
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]
edges_i = {}
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    edges_i[a, b] = i
    edges_i[b, a] = i

root = 0
parents = [None] * N
stack = [(root, None)]
while stack:
    v, p = stack.pop()
    parents[v] = p
    for u in graph[v]:
        if u == p:
            continue
        stack.append((u, v))

lca = DoublingLCA(graph=graph, max_v=N - 1, root=root)
constraints = [0] * M

for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    ancestor = lca.lca(v, u)
    while v != ancestor:
        constraints[i] |= 1 << edges_i[v, parents[v]]
        v = parents[v]
    while u != ancestor:
        constraints[i] |= 1 << edges_i[u, parents[u]]
        u = parents[u]






def count(edges_bin):
    cnt = 0
    while edges_bin > 0:
        cnt += edges_bin & 1
        edges_bin >>= 1
    return pow(2, N - 1 - cnt)





ans = 0
for choice in range(1, 1 << M):
    cnt = 0
    edges = 0
    for i in range(choice.bit_length()):
        if choice >> i & 1:
            cnt += 1
            edges |= constraints[i]
    ans += count(edges) * (-1) ** (cnt - 1)
print(2 ** (N - 1) - ans)

Solution (Python):
from collections import defaultdict, Counter

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

cnt = [set() for _ in range(M)]
def dfs(cur, pre, dest, i) :
  if cur == dest :
    return True
  
  for nex, j in ab[cur] :
    if nex == pre :
      continue
    if dfs(nex, cur, dest, i) :
      cnt[i].add(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 = set([])
  for j in range(M) :
    if i & (1 << j) :
      s |= cnt[j]
      sgn *= -1
  ret += sgn * (1 << (N - 1 - len(s)))

print(ret)

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

g = [[] for _ in range(n)]
edge = {}


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

m = int(input())


def dfs(u,v):
    visited = [False]*n
    visited[u] = True
    stack = [u]
    prev = [-1]*n
    while stack:
        uu = stack.pop()
        for vv in g[uu]:
            if not visited[vv]:
                visited[vv] = True
                prev[vv] = uu
                stack.append(vv)
        if prev[v] != -1:
            break
    bin_edge = 0
    head = v
    while head != u:
        bin_edge += 1 << edge[(head, prev[head])]
        head = prev[head]
    return bin_edge

intv = [0]*m

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


mm = 1 <<m

ans = 0

for i in range(mm):
    a = 0
    cnt = 0
    for j in range(m):
        if (i >> j) & 1:
            cnt += 1
            a = a | intv[j]
    white = str(bin(a)).count('1')
    ans += ((-1)**(cnt))*2**(n-1-white)

print(abs(ans))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n 
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

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

passing=[] 
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)

for i in range(1,2**m):
  i_ct=popcount(i)
  condition=0
  for j in range(m):
    if i&(1<<j):
      condition=condition|passing[j]
  cond_ct=popcount(condition) 

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n 
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

def popcount(x):
  return bin(x).count("1")

passing=[] 
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)

for i in range(1,2**m):
  i_ct=popcount(i)
  condition=0
  for j in range(m):
    if i&(1<<j):
      condition=condition|passing[j]
  cond_ct=popcount(condition) 

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)

Solution (Python):
from collections import deque


def getPath(adj, start, goal):
    q = deque()
    q.appendleft((start, 0))
    while len(q):
        cur, p = q.pop()
        if cur == goal:
            return p
        for nxt, nhop in adj[cur]:
            if 2**nhop & p:
                continue
            npath = p | 2**nhop
            q.appendleft((nxt, npath))


def bitcount(x):
    return bin(x).count("1")


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add((b-1, i))
        adj[b-1].add((a-1, i))
    M = int(input())
    dp = [0] * (2**M)
    for i in range(M):
        u, v = map(int, input().split())
        path = getPath(adj, u-1, v-1)
        for j in range(2**i):
            dp[j + 2**i] = dp[j] | path
    ans = 0
    for i in range(2**M):
        ans += (-1) ** bitcount(i) * 2 ** (N - bitcount(dp[i]) - 1)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def dfs(start, goal, tree):
    """startからgoalまでの木上のpathを出力する"""
    q = deque([start])
    visited = {}
    visited[start] = -1
    while True:
        pos = q.pop()
        if pos == goal:
            break
        for child in tree[pos]:
            if child in visited:
                continue
            visited[child] = pos
            q.append(child)
    res = []
    pos = goal
    while True:
        par = visited[pos]
        if par == -1:
            break
        res.append((min(par, pos), max(par, pos)))
        pos = par
    return res


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i
  

li_path = [0] * m
for i in range(m):
    s, g = path[i]
    s -= 1
    g -= 1
    res = dfs(s, g, tree)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)

Solution (Python):
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i


def dfs(par, pos, goal):
    if pos == goal:
        return True
    for child in tree[pos]:
        if child == par:
            continue
        if dfs(pos, child, goal):
            res.append((min(pos, child), max(pos, child)))
            return True
    return False
  

li_path = [0] * m
for i in range(m):
    res = []
    s, g = path[i]
    s -= 1
    g -= 1
    dfs(-1, s, g)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)

Solution (Python):





from collections import deque

N = int(input())
adj = [[] for i in range(N + 1)] 
ve = {} 
for i in range(1, N) : 
    a, b = map(int,input().split())
    adj[a].append(b); adj[b].append(a)
    ve[(a, b)] = ve[(b, a)] = i




l = [[set() for j in range(N + 1)] for i in range(N + 1)]
q = deque()
for i in range(1, N + 1):
    r = [False] * (N + 1)
    q.append(i); r[i] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if r[v]:
                continue
            l[i][v].update(l[i][u])            
            l[i][v].add(ve[(u, v)])
            q.append(v)
            r[v] = True

'''
for i in range(1, N + 1):
    for j in range(i, N + 1):
        print(i, j, l[i][j])
'''
M = int(input())
c = [set()]
for i in range(1, M + 1): 
    u, v = map(int,input().split())
    c.append((u, v))

ans = 2 ** (N - 1)
for k in range(1, 1 << M): 
    V = set()
    d = 0 
    for i in range(1, M + 1):
        if k >> (i - 1) & 1:
            d += 1
            u, v = c[i]
            V |= l[u][v]
    
    temp = 2 ** (N - 1 - len(V))
    
    if d % 2 == 1:
        ans -= temp
    elif d % 2 == 0:
        ans += temp

print(ans)