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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline

import numpy as np

N = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(N - 1))
M = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(M))

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


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


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


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


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

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline

import numpy as np

N = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(N - 1))
M = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(M))

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


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


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


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


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

n_edges = popcnt(S)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline

import numpy as np

N = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(N - 1))
M = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(M))

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


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


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


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


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

n_edges = popcnt(S)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/submissions/9619555

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

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

M = int(readline())


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


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


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


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


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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/submissions/9619555

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

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

M = int(readline())


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


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


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


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


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

Submission status: Accepted

Solution code:
from collections import defaultdict


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


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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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


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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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


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

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

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
# original: https://atcoder.jp/contests/abc152/submissions/9634969
# test the difference between implementation of popcount
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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


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

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

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

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


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


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

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

Submission status: Accepted

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

pc=[set() for _ in range(M)] #各制約で使用する辺の集合

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  N = int(input())
  E = [[] for _ in range(N)]
  # E:頂点a,bをつなぐ枝にiという番号をふる。
  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))
  
  # dfs(u,v,p):uからvまでのパス上にある頂点をEGにセットする。
  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[i]:i番目の制約のパス上にある頂点
  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:iのビットが立っているところの制約のパス上にある頂点の集合。
    # bc:iのビットが立っている個数。
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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