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
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]
m = int(input())
U = [list(map(int,input().split())) for i in range(m)]

for i in range(n-1):
    for j in range(2):
        C[i][j] -= 1
for i in range(m):
    for j in range(2):
        U[i][j] -= 1

B = [[0] * (m) for i in range(n-1)]

M = [[] for i in range(n)]
for i in range(n-1):
    M[C[i][0]].append([C[i][1], 1])  
    M[C[i][1]].append([C[i][0], 1])  

E = [[-1] * n for i in range(n)]
for i in range(n-1):
    E[C[i][0]][C[i][1]] = i
    E[C[i][1]][C[i][0]] = i  

F = [[] for i in range(m)]
import heapq

for mm in range(m):
    uu = U[mm][0]
    vv = U[mm][1]

    D = [float("inf")] * n  
    P = [-1] * n  
    D[uu] = 0
    V = [0] * n  
    Q = []  
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])

    
    tt = vv
    while tt != uu:
        ss = P[tt]
        F[mm].append(E[ss][tt])
        
        tt = ss



for i in range(m):
    for j in F[i]:
        B[j][i] = 1



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



BB = [[] for i in range(m+1)]
for i in range(len(B)):
    BB[sum(B[i])].append(B[i][:])

CC = []
for i in range(len(BB)):
    for j in range(len(BB[i])):
        CC.append(BB[i][j])
B=CC
import itertools

G = [0] * (2**m)
G[0] = 1
for i in range(n-1):
    ii = 0
    K = []
    for j in range(m):
        if B[i][j] == 1:
            K.append(j)
        ii += B[i][j] * M2[m-1-j]
    

    GG = G[:]
    for jj in range(2**m):
        GG[jj | ii] += G[jj]
    G = GG[:]
    
    
    
    
    
    
    
    
    
    
    
    

print(G[-1])

Solution (Python):
def main():
    import sys
    from collections import defaultdict, deque
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, N):
            
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 2 ** 31 - 1
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) // 2
                self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret = min(ret, self.seg_min[last])
                first = first // 2
                last = last // 2 - 1
            return ret

    def EulerTour(adj, root):
        st = [root]
        ret = []
        seen = [0] * len(adj)
        par = [0] * len(adj)
        depth = [0] * len(adj)
        while st:
            v = st.pop()
            if seen[v]:
                ret.append(v)
                continue
            ret.append(v)
            seen[v] = 1
            if par[v] != 0:
                st.append(par[v])
            for u in adj[v]:
                if seen[u] == 0:
                    st.append(u)
                    par[u] = v
                    depth[u] = depth[v] + 1

        return ret, depth, par

    def f(a, b):
        return a*100+b

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

    et, depth, par = EulerTour(adj, 1)
    segtree = SegTree(len(et) + 1)
    left = [-1] * (N + 1)
    right = [-1] * (N + 1)
    for i, v in enumerate(et):
        segtree.update(i + 1, depth[v])
        if left[v] < 0:
            left[v] = i
        right[v] = i

    M = int(input())
    edge2cond = defaultdict(int)
    for j in range(M):
        a, b = map(int, input().split())
        lca_depth = segtree.query(min(left[a], left[b]) + 1, max(right[a], right[b]) + 1)
        prev = a
        for i in range(depth[a] - lca_depth):
            parent = par[prev]
            edge2cond[parent*100+prev] += 2**j
            prev = parent
        prev = b
        for i in range(depth[b] - lca_depth):
            parent = par[prev]
            edge2cond[parent*100+prev] += 2**j
            prev = parent

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()
    dp = [[0] * (2**M) for _ in range(N)]
    dp[0][0] = 1
    for i, v in enumerate(seq):
        if v == 1:
            continue
        for mask in range(2**M):
            u = par[v]
            mask_new = edge2cond[u*100+v]

            dp[i+1][mask] += dp[i][mask]
            dp[i+1][mask | mask_new] += dp[i][mask]
    print(dp[-1][-1])
    
    


if __name__ == '__main__':
    main()

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

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        
        path.add(u*N+_u)
        u = _u
    while v!=w:
        _v = parent[v]
        
        path.add(v*N+_v)
        v = _v
    P.append(path)


ans = 0
n1 = N-1
for k in range(2**M):
    path = set()
    n = 0
    for i, p in enumerate(P):
        if (k>>i)&1:
            path |= p
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, n1-len(path))
    
print(pow(2, N-1) - ans)

Solution (Python):
N = int(input())
from collections import defaultdict
G = defaultdict(list)
EdaNum = {}
Ki = [[float('inf')]*(N+1) for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(min(a,b),max(a,b))] = i
    Ki[a][b] = 1
    Ki[b][a] = 1

Next = [[-1]*(N+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        Next[i][j] = j

        
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if Ki[i][k] + Ki[k][j] < Ki[i][j]:
                Ki[i][j] = Ki[i][k] + Ki[k][j]
                Next[i][j] = Next[i][k]

M = int(input())
MM = [set() for i in range(M)]


for i in range(M):
    u,v = map(int,input().split())
    now = u
    while now != v:
        nex = Next[now][v]
        MM[i].add(EdaNum[(min(now,nex),max(now,nex))])
        now = nex
        

import itertools
zero1 = [0,1]
ans = 0

for i in itertools.product(zero1,repeat = M):
    
    count = 0
    root = set()
    for j in range(M):
        if i[j] == 0:
            count += 1
        else:
            root |= MM[j]
    
    if (M-count)%2 ==0:
        ans += pow(2,N-1-len(root))
    else:
        ans -= pow(2,N-1-len(root))
        
print(ans)

Solution (Python):
N = int(input())
inf = 10**18
G = [[inf]*N for _ in range(N)]
edges = [[-1]*N for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1][b-1] = i
    edges[b-1][a-1] = i
use = [-1]*N
que = [0]
use[0] = 0
while que:
    v = que.pop()
    u = use[v]
    for nv in range(N):
        if edges[v][nv] == -1 or use[nv] != -1:
            continue
        i = edges[v][nv]
        use[nv]=u^(1<<i)
        que.append(nv)
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]
used = [0]*(1<<M)
cnt = [0]*(1<<M)
ans = 0
for s in range(1, 1<<M):
    for i in range(M):
        if (s>>i)&1:
            u, v = uv[i]
            u, v = u-1, v-1
            p = s^(1<<i)
            used[s] = used[p]|(use[u]^use[v])
            cnt[s] = cnt[p]^1
            break
    res = 0
    for i in range(N-1):
        if used[s]&(1<<i):
            res+=1
    ans+=(-1)**cnt[s]*pow(2, N-1-res)
print(pow(2, N-1)+ans)

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u, v, pu=-1):
        if u == v: return True
        for cu in to[u]:
            if cu == pu: continue
            if dfs(cu, v, u):
                path.append(uvtoi[u, cu])
                return True
        return False

    to = defaultdict(list)
    n = II()
    uvtoi = {}
    for i in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
        uvtoi[a, b] = i
        uvtoi[b, a] = i
    m = II()
    itoj = defaultdict(list)
    for j in range(m):
        u, v = MI1()
        path = []
        dfs(u, v)
        
        for i in path: itoj[i].append(j)
    
    en = len(itoj)
    dp = [[0] * (1 << m) for _ in range(en + 1)]
    dp[0][0] = 1
    for i, jj in enumerate(itoj.values()):
        mask = sum(1 << j for j in jj)
        for bit in range(1 << m):
            pre = dp[i][bit]
            if pre == 0: continue
            dp[i + 1][bit | mask] += pre
            dp[i + 1][bit] += pre
    
    ans=dp[-1][-1]*pow(2,n-1-en)
    print(ans)

main()

Solution (Python):
INF = 1 << 30

n = int(input())

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

m = int(input())

u = [0 for i in range(m)]
v = [0 for i in range(m)]
ls = [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

    cost = [INF for j in range(n)]
    cost[u[i]] = 0
    st = [u[i]]
    pre = [-1 for j in range(n)]
    pre[u[i]] = -2

    while len(st) > 0:
        now = st.pop()
        for to in g[now]:
            if pre[to] == -1:
                pre[to] = now
                st.append(to)
    
    pos = v[i]
    while pos != u[i]:
        for j in range(len(g[pos])):
            to = g[pos][j]
            if to == pre[pos]:
                ls[i] |= 1<<num[pos][j]
                pos = to
                break

ans = 0

for bit in range(1<<m):
    cnt = 0
    val = 0
    for i in range(m):
        if ((bit>>i)&1) == 1:
            cnt += 1
            val |= ls[i]
    
    pcnt = 0
    for i in range(n):
        if ((val>>i)&1) == 1:
            pcnt += 1
    
    nokori = n-1-pcnt

    if cnt%2 == 0:
        ans += 2**nokori+1
    else:
        ans -= 2**nokori+1

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
edges = []
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
        edges.append((b, a))
    else:
        edge_dict[(a, b)] = i
        edges.append((a, b))
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
state = [set() for _ in range(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 edge_dict:
            state[i].add(edge_dict[(uu, vv)])


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

dp[0][0] = 1
a, b = edges[0]
status = 0
for i, st in enumerate(state):
    if 0 in st:
        status |= 1 << i
dp[0][status] += 1
 
for i, (a, b) in enumerate(edges):
    if i == 0:
        continue
    status = 0
    for j, st in enumerate(state):
        if i in st:
            status |= 1 << j
    for k in range(2**m):
        
        dp[i][k | status] += dp[i-1][k]
        
        dp[i][k] += dp[i-1][k]
 
print(dp[-1][-1])

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

D = {1<<i: i for i in range(50)}
Z = [0] * (1<<M)
ans = 0
CC = [0] * N
BC = [0] * (1<<17)
for m in range(1, 1<<17):
    a = m & (-m)
    BC[m] = BC[m^a] + 1
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]]
    
    aa = Z[m]
    bc = BC[aa % (1<<17)]
    aa >>= 17
    bc += BC[aa % (1<<17)]
    aa >>= 17
    bc += BC[aa]
    CC[N - 1 - bc] += (1 if BC[m%1024] + BC[m>>10] & 1 == 0 else -1)

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

Solution (Python):
from collections import deque
n = int(input())
Graph = [[] for _ in range(n)]
edge = {}
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    Graph[a].append(b)
    Graph[b].append(a)
    edge[1000*a+b] = i
    edge[1000*b+a] = i

data = []

def f(u,v):
    prev = [u]*n
    used = [False]*n
    que = deque([u])
    while que:
        now = que.popleft()
        for nex_v in Graph[now]:
            if used[nex_v]:continue
            prev[nex_v] = now
            used[nex_v] = True
            que.append(nex_v)
            if nex_v == v:
                break
    path = [v]
    path_edge = []
    t = v
    while prev[t] != u:
        path.append(prev[t])
        path_edge.append(edge[1000*t+prev[t]])
        t = prev[t]
    path_edge.append(edge[1000*t+prev[t]])
    path.append(u)
    return path_edge

m = int(input())
for i in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    path = f(u,v)
    data.append(path[::-1])


ans = 2**(n-1)
for i in range(1,1<<m):
    now = []
    for j in range(m):
        if i>>j&1:
            now.append(j)

    this = [True]*(n-1)
    for j in now:
        for k in data[j]:
            this[k] = False

    ponta = 1
    q = 0
    for j in range(n-1):
        if this[j]:
            ponta *= 2
            q += 1

    if len(now)%2 == 0:
        ans += ponta
    else:
        ans -= ponta

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

D = {1<<i: i for i in range(50)}
Z = [0] * (1<<M)
ans = 0
CC = [0] * N
BC = [0] * (1<<20)
for m in range(1, 1<<20):
    a = m & (-m)
    BC[m] = BC[m^a] + 1
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]]
    
    aa = Z[m]
    bc = BC[aa % (1<<10)]
    aa >>= 10
    bc += BC[aa % (1<<20)]
    aa >>= 20
    bc += BC[aa]
    CC[N - 1 - bc] += (1 if BC[m] % 2 == 0 else -1)

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

Solution (Python):
def main():
    from itertools import combinations
    n = int(input())
    ab = [tuple(sorted(list(map(int, input().split())))) for _ in [0]*(n-1)]
    m = int(input())
    uv = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    d = dict()
    for i, (a, b) in enumerate(ab):
        d[(a-1, b-1)] = i

    def tree_path(root, goal):
        d = [-1]*n  
        d[root] = 0
        q = [root]
        cnt = 0
        while q:  
            cnt += 1
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] == -1:
                        d[j] = cnt
                        qq.append(j)
            q = qq
        now = goal
        path = [goal]
        while True:
            dist = d[now]
            for i in g[now]:
                if d[i] < dist:
                    now = i
                    path.append(i)
                    break
            if dist == 1:
                break
        return path

    seiyaku = [set() for _ in [0]*m]

    for i, (u, v) in enumerate(uv):
        path = tree_path(u-1, v-1)
        for j in range(len(path)-1):
            x, y = min(path[j], path[j+1]), max(path[j], path[j+1])
            seiyaku[i].add(d[(x, y)])

    

    cnt = 2**(n-1)

    for i in range(1, m+1):
        flag = 1
        if i % 2 == 1:
            flag = -1
        cc = combinations(list(range(m)), i)
        
        for c in cc:
            
            s = set()
            for j in c:
                s |= seiyaku[j]
            cnt += (2**(n-1-len(s)))*flag
            
    print(cnt)


main()

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


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 = bin(i).count('1')
    bit = 0
    k = i
    while k:
        b = k & -k
        j = b.bit_length() - 1
        bit |= conditions[j]
        k ^= b
    free_link_cnt = n - 1 - bin(bit).count('1')
    val = 2 ** free_link_cnt
    if cnd_cnt % 2:
        ans -= val
    else:
        ans += val
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))

D = {1<<i: i for i in range(50)}
Z = [0] * (1<<M)
ans = 0
CC = [0] * N
BC = [0] * (1<<M)
for m in range(1, 1<<M):
    a = m & (-m)
    BC[m] = BC[m^a] + 1
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 - bin(Z[m]).count("1")] += (1 if BC[m] % 2 == 0 else -1)

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

Solution (Python):
from itertools import product as p
n=int(input())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append([b,i])
    s[b].append([a,i])
m=int(input())
l=[]
for i in range(m):
    u,v=map(int,input().split())
    a=[[]for i in range(n+1)]
    a[u]=[]
    q=[u]
    while q:
        t=q.pop(0)
        d=0
        for i,j in s[t]:
            if a[i]==[]:
                a[i]=a[t]+[j]
                q.append(i)
                if i==v:
                    d=1
                    break
        if d==1:
            break
    l.append(a[v])
for i in range(m):l[i]=set(l[i])
s=[0]*(m+1)
for i in p([0,1],repeat=m):
    d=set([])
    if sum(i)!=0:
        for j in range(m):
            if i[j]:
                d|=l[j]
        s[sum(i)]+=pow(2,n-1-len(d))
l=0
for i in range(1,m+1):
    l+=((-1)**(i-1))*s[i]
print(pow(2,n-1)-l)

Solution (Python):
N=int(input())
ab=[list(map(int,input().split())) for i in range(N-1)]
M=int(input())
uv=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
node=[[-1]*(N+1) for i in range(N-1)]
for i in range(N-1):
    a,b=ab[i]
    flag=[0]*(N+1)
    flag[a]=1
    flag[b]=1
    node[i][a]=0
    que=[a]
    while que:
        u=que.pop()
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                node[i][v]=0
                que.append(v)
    node[i][b]=1
    que=[b]
    while que:
        u=que.pop()
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                node[i][v]=1
                que.append(v)
dp=[[0]*2**M for i in range(N)]
dp[0][0]=1
for i in range(N-1):
    h=node[i]
    num=0
    for j in range(M):
        u,v=uv[j]
        if h[u]==h[v]:
            continue
        else:
            num+=2**j
    dp[i+1]=dp[i][:]
    for j in range(2**M):
        dp[i+1][j|num]+=dp[i][j]
print(dp[-1][-1])

Solution (Python):
n = int(input())
ab = {i: [] for i in range(n)}
for j in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    ab[a].append((b, j))
    ab[b].append((a, j))


def dfs(a, b, d=[], c=-1):
    if a == b:
        return d
    for i in ab[a]:
        if i[0] == c:
            continue
        e = dfs(i[0], b, d + [i[1]], a)
        if len(e) != 0:
            return set(e)
    return set()


m = int(input())
ms = []
for _ in range(m):
    u, p = [int(i) - 1 for i in input().split()]
    ms.append(dfs(u, p))

ans = 0
for i in range(1 << m):
    k = 0
    a = set()
    for j in range(m):
        if (i >> j) & 1 == 1:
            k += 1
            a |= ms[j]
    if k % 2 == 1:
        ans += 2 ** (n - 1 - len(a))
    elif k != 0:
        ans -= 2 ** (n - 1 - len(a))
            
print(2**(n-1)-ans)

Solution (Python):
from collections import deque


def solve(n, edge_list, m, cond_list):

    g = [[] for _ in range(n)]

    for a, b in edge_list:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    cond_mat = [[0] * m for _ in range(n - 1)]

    for i in range(m):
        u, v = cond_list[i]
        parent_list = [-1] * n
        p = u - 1
        parent_list[p] = p
        queue = deque([p])
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p]:
                if parent_list[q] == -1:
                    parent_list[q] = p
                    queue.append(q)
        q = v - 1
        p = parent_list[q]
        while q != u - 1:
            if (p + 1, q + 1) in edge_list:
                k = edge_list.index((p + 1, q + 1))
            else:
                k = edge_list.index((q + 1, p + 1))
            cond_mat[k][i] = 1
            p, q = parent_list[p], parent_list[q]

    
    cond_vec = [0] * (n - 1)
    for k in range(n - 1):
        for i in range(m):
            cond_vec[k] += cond_mat[k][i] * (2 ** i)
    
    
    dp = [[0] * (2 ** m) for _ in range(n)]
    dp[0][0] = 1
    for k in range(n - 1):
        for i in range(2 ** m):
            dp[k + 1][i] += dp[k][i]
            dp[k + 1][i | cond_vec[k]] += dp[k][i]
    
    return dp[-1][-1]


def main():
    n = int(input())
    edge_list = []
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge_list.append((a, b))
    m = int(input())
    cond_list = []
    for _ in range(m):
        u, v = map(int, input().split())
        cond_list.append((u, v))
    res = solve(n, edge_list, m, cond_list)
    print(res)


def test():
    assert solve(3, [(1, 2), (2, 3)], 1, [(1, 3)]) == 3
    assert solve(2, [(1, 2)], 1, [(1, 2)]) == 1
    assert solve(5, [(1, 2), (3, 2), (3, 4), (5, 3)], 3, [(1, 3), (2, 4), (2, 5)]) == 9


if __name__ == "__main__":
    test()
    main()

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

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 - bin(Z[m]).count("1")] += (1 if bin(m).count("1") % 2 == 0 else -1)

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

Solution (Python):
import os
import sys
from functools import lru_cache

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

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


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 = {}
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    edges[a, b] = i
    edges[b, a] = i


@lru_cache(maxsize=None)
def path(v, u, p):
    if v == u:
        return [u]
    for nv in graph[u]:
        if nv == p:
            continue
        ret = path(v, nv, u)
        if ret is not None:
            return ret + [u]
    return None



constraints = [0 for _ in range(N - 1)]
for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    pp = path(v, u, None)
    for pv, pu in zip(pp, pp[1:]):
        constraints[edges[pv, pu]] |= 1 << i







dp = [0 for _ in range(1 << M)]
dp[0] = 1
for c in constraints:
    for i in reversed(range(1 << M)):
        dp[i | c] += dp[i]
print(dp[-1])