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:



Sample input:
3
1 2
2 3
1
1 3


Sample output:
3

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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[i-th item][fills uv as st]
dp = [[0] * 2**m for _ in range(n - 1)]
# White
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):
        # Fill black
        dp[i][k | status] += dp[i-1][k]
        # Fill white
        dp[i][k] += dp[i-1][k]
 
print(dp[-1][-1])

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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])

#print(data)
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)

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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:  # BFS
            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)])

    # print(seiyaku)

    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)
        # print(list(cc))
        for c in cc:
            # print(c)
            s = set()
            for j in c:
                s |= seiyaku[j]
            cnt += (2**(n-1-len(s)))*flag
            # print((2**(n-1-len(s)))*flag)
    print(cnt)


main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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
# MOD = 998244353

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

# N <= 50
# M <= 20


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

# for c in constraints:
#     import numpy as np
#
#     print(np.binary_repr(c, M))

# or したときに全部 True になる組み合わせの数
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])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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]

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

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

n_edges = popcnt(S)

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

Submission status: Accepted

Solution code:
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 dfs(g,root,w):
    parent = [-1]*n
    enum = [-1]*n
    q = [root]
    while q:
        v = q.pop()
        for c,i in g[v]:
            if c != parent[v]:
                parent[c] = v
                enum[c] = i
                q.append(c)
    a = 0
    #print(parent,enum)
    while w != root:
        a |= 1<<enum[w]
        w = parent[w]
    return a
    

###################################
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,m = [int(i) for i in readline().split()]
#d = [int(i) for i in readline().split()]
MOD = 10**9+7

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

m = int(input())

#使う要素のbitmask
res = [0]*m
for i in range(m):
    v,w = [int(i)-1 for i in readline().split()]
    res[i] = dfs(g,v,w)

ans = 1<<(n-1)
M = 1<<m
#print(res)
for mask in range(1,M):
    r = 0
    for j in range(m):
        if mask&(1<<j): r |= res[j]
    
    r = popcnt(r)
    c = popcnt(mask)
    if c%2:
        ans -= 1<<(n-1-r)
    else:
        ans += 1<<(n-1-r)

print(ans)

Submission status: Accepted

Solution code:
from copy import copy

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

edge_set = [set() for i in range(n)]
edge_id = 0

def dfs(p,v,se):
    global edge_id
    edge_set[v] = se
    for to in G[v]:
        if to != p:
            nset = copy(se)
            nset.add(edge_id)
            edge_id += 1
            dfs(v,to,nset)

dfs(-1,0,set())

m = int(input())
edge_set2 = []
for i in range(m):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    edge_set2.append(edge_set[a]^edge_set[b])

from itertools import combinations
ans = 0
for i in range(m):
    op = -1 if i%2 else 1
    for c in combinations(range(m), i+1):
        s = set()
        for j in c:
            s |= edge_set2[j]
        rem = n-1 - len(s)
        ans += op*(1<<rem)
ans = 2**(n-1) - ans
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(cur, pre, g, par, od):
    par[cur] = pre
    od.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, par, od)

par = [-1] * n
od = []
dfs(0, -1, g, par, od)

def lca(a, b, par):
    ps = set()
    q = a
    while q != -1:
        ps.add(q)
        q = par[q]
    while b != -1:
        if b in ps:
            return b
        b = par[b]
    raise

m = ni()
cons = [0] * n
for i in range(m):
    u, v = na()
    u -= 1
    v -= 1
    lc = lca(u, v, par)
    while u != lc:
        cons[u] |= 1<<i
        u = par[u]
    while v != lc:
        cons[v] |= 1<<i
        v = par[v]

def st(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] += b[j]
    return b

def ist(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] -= b[j]
    return b

dp = [1] * (1<<m)
for cur in range(1,n):
    for i in range(1<<m):
        if (i&cons[cur]) == cons[cur]:
            dp[i] *= 2

# dp = [None for _ in range(n)]
# for i in range(n-1,-1,-1):
#     cur = od[i]
#     my = [0] * (1<<m)
#     my[0] = 1
#     if cur != 0:
#         my[cons[cur]] += 1
#     my = st(my, m)
#
#     for e in g[cur]:
#         if e == par[cur]: continue
#         for j in range(1<<m):
#             my[j] = my[j] * dp[e][j]
#     dp[i] = my

    # dp[i] = ist(my, m)

dp = ist(dp, m)

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

Submission status: Runtime Error

Solution code:
#!python3

class Node:
    
    def __init__(self, num):
        self.num = num
        self.depth = 0
        self.parent = (None, None)


LI = lambda: list(map(int, input().split()))

# input
N = int(input())
AB = [LI() for _ in range(N - 1)]
M = int(input())
UV = [LI() for _ in range(M)]

# params
links = [[] for _ in range(N)]
nodes = [Node(i) for i in range(N)]
w = []
p2 = [2 ** i for i in range(N + 1)]


def create_links():
    for i in range(N - 1):
        a, b = AB[i][0] - 1, AB[i][1] - 1
        links[a].append((b, i))
        links[b].append((a, i))


def create_tree(v, p=-1):
    for u, i in links[v]:
        if u == p:
            continue
        nodes[u].parent = (nodes[v], i)
        nodes[u].depth = nodes[v].depth + 1
        create_tree(u, v)


def between_links(s, t):
    x = nodes[s]
    y = nodes[t]
    if x.depth > y.depth:
        x, y = y, x
    s = set()
    while x.depth < y.depth:
        y, i = y.parent
        s.add(i)
    while x is not y:
        x, i = x.parent
        y, j = y.parent
        s.add(i)
        s.add(j)
    return s


def create_between_links():
    for u, v in UV:
        s = between_links(u - 1, v - 1)
        w.append(s)


def main():
    create_links()
    create_tree(0)
    create_between_links()
    
    ans = 0
    n = p2[M]
    for i in range(n):
        f = 0
        s = set()
        for j in range(M):
            if i >> j & 1:
                f += 1
                s |= w[j]
        v = p2[N - 1 - len(s)]
        if f % 2 == 0:
            ans += v
        else:
            ans -= v
    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

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

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

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [tuple(map(int,input().split())) for _ in range(N - 1)]
M = int(input())
uv = [tuple(map(int,input().split())) for _ in range(M)]
route = [[] for _ in range(N)]

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

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [tuple(map(int,input().split())) for _ in range(N - 1)]
M = int(input())
uv = [tuple(map(int,input().split())) for _ in range(M)]
route = [[] for _ in range(N)]

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

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [tuple(map(int,input().split())) for _ in range(N - 1)]
M = int(input())
uv = [tuple(map(int,input().split())) for _ in range(M)]
route = [[] for _ in range(N)]

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

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

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