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:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
dist = [[100]*(N+1) for _ in range(N+1)]  # 2点間の最短距離
edges = {}

for i in range(N-1):
    a,b = MI()
    dist[a][b] = 1
    dist[b][a] = 1
    edges[(a,b)] = i
    edges[(b,a)] = i

for i in range(1,N+1):
    dist[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

M = I()
A = []  # uとvを結ぶ経路上にある辺の集合
for _ in range(M):
    u,v = MI()
    B = set()
    while True:
        if dist[u][v] == 1:
            B.add(edges[(u,v)])
            break
        else:
            for i in range(1,N+1):
                if dist[u][i] == dist[u][v]-1 and dist[i][v] == 1:
                    B.add(edges[(i,v)])
                    v = i
                    break
    A.append(B)


def popcount(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


# 包除原理

ans = 0
for i in range(2**M):
    C = set()
    for j in range(M):
        if (i >> j) & 1:
            C |= A[j]
    l = len(C)
    a = popcount(i)
    a %= 2
    ans += (-1)**a * 2**(N-1-l)

print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
dist = [[100]*(N+1) for _ in range(N+1)]  # 2点間の最短距離
edges = {}

for i in range(N-1):
    a,b = MI()
    dist[a][b] = 1
    dist[b][a] = 1
    edges[(a,b)] = i
    edges[(b,a)] = i

for i in range(1,N+1):
    dist[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

M = I()
A = []  # uとvを結ぶ経路上にある辺の集合
for _ in range(M):
    u,v = MI()
    B = set()
    while True:
        if dist[u][v] == 1:
            B.add(edges[(u,v)])
            break
        else:
            for i in range(1,N+1):
                if dist[u][i] == dist[u][v]-1 and dist[i][v] == 1:
                    B.add(edges[(i,v)])
                    v = i
                    break
    A.append(B)

# 包除原理

ans = 0
for i in range(2**M):
    C = set()
    a = 0
    for j in range(M):
        if (i >> j) & 1:
            C |= A[j]
            a += 1
    l = len(C)
    a %= 2
    ans += (-1)**a * 2**(N-1-l)

print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
dist = [[100]*(N+1) for _ in range(N+1)]  # 2点間の最短距離
edges = {}

for i in range(N-1):
    a,b = MI()
    dist[a][b] = 1
    dist[b][a] = 1
    edges[(a,b)] = i
    edges[(b,a)] = i

for i in range(1,N+1):
    dist[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])

M = I()
A = []  # uとvを結ぶ経路上にある辺の集合
for _ in range(M):
    u,v = MI()
    B = set()
    while True:
        if dist[u][v] == 1:
            B.add(edges[(u,v)])
            break
        else:
            for i in range(1,N+1):
                if dist[u][i] == dist[u][v]-1 and dist[i][v] == 1:
                    B.add(edges[(i,v)])
                    v = i
                    break
    A.append(B)

# 包除原理

ans = 0
for i in range(2**M):
    C = set()
    a = 0
    for j in range(M):
        if (i >> j) & 1:
            C = C | A[j]
            a = 1-a
    l = len(C)
    if a == 0:
        ans += pow(2,N-1-l)
    else:
        ans -= pow(2,N-1-l)

print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def popcnt(x):
    c = 0
    while x>0:
        c += x%2
        x >>= 1
    return c

def dfs(u,v,p):
    global d
    d[u][v] = p
    for x in dst[v]:
        if u!=x and d[u][x]==0:
            p |= 1<<dst[v][x]
            dfs(u,x,p)
            p ^= 1<<dst[v][x]

n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    a,b = inm()
    dst[a][b] = dst[b][a] = i

m = inn()
u = []
v = []
for i in range(m):
    uu,vv = inm()
    u.append(uu)
    v.append(vv)

if False and n==2 and m==1:
    print(0)
    exit()

d = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    dfs(i,i,0)
dd = []
for i in range(m):
    dd.append(d[u[i]][v[i]])
ddprint(dst)
ddprint(d)
ddprint(u)
ddprint(v)
ddprint(dd)

y = 0
for i in range(1,2**m):
    nbits = x = 0
    for j in range(m):
        if (i>>j)%2>0:
            x |= dd[j]
            nbits += 1
    nsegs = popcnt(x)
    s = 2*(nbits%2)-1
    y += s*2**(n-1-nsegs)
print(2**(n-1)-y)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        i = 0
        for x, y in edges:
            self.add_edge(x,y,i)
            i += 1
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.path_bit = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y, i):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add((y,i))
        self.edges[y].add((x,i))

    def dfs(self):
        next_set = [self.root]
        self.path_bit[self.root] = 0
        while next_set:
            p = next_set.pop()
            for q, i in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.path_bit[q] = self.path_bit[p] | 1 << i
                    self.doubling[0][q] = p
                    next_set += [q]

    def get_list(self, u, v):
        if self.decrement:
            u -= 1
            v -= 1
        return self.path_bit[u] ^ self.path_bit[v]

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.Graph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)

        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()

#################################################################################################

from itertools import combinations

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 = int(input())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))

lca = LCA(N, 1, edges, decrement=True)

M = int(input())
edges2 = []
for _ in range(M):
    x, y = map(int, input().split())
    edges2.append((x,y))

res = pow(2,N-1)
for m in range(1,M+1):
    for a in combinations(edges2, m):
        temp = 0
        for b in a:
            temp |= lca.get_list(*b)
        res += (1-2*(m%2))*pow(2,N -1 - popcnt(temp))

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict


def get_path(from_node, to_node, adj, nodes2edge):
    # from_nodeからto_nodeまでの最短パスで通るedgeを返す

    def dfs(node, parent, edges):
        if node == to_node:
            return edges
        min_path = None
        for child in adj[node]:
            if child == parent:
                continue
            path = dfs(child, node, edges + [nodes2edge[(node, child)]])
            if path is None:
                continue
            if min_path is None or len(min_path) > len(path):
                min_path = path
        return min_path

    return dfs(from_node, None, list())


def count_bits(n):
    return len([i for i in range(len('{:b}'.format(n))) if (n >> i) & 1 == 1])


def main():
    N = int(input())
    adj = defaultdict(list)
    nodes2edge = defaultdict(lambda :-1)
    for i in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
        nodes2edge[(a, b)] = i
        nodes2edge[(b, a)] = i
    M = int(input())
    constraints = [list(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(M)]
    # 各制約を「パス u->v 上の辺はすべて白」として扱い、包除原理で計算
    base = [0] * M  # 各制約で出てくる最短 u->v パス で通るedgeの2進表記
    for m, constraint in enumerate(constraints):
        u, v = constraint
        path = get_path(u, v, adj, nodes2edge)
        v = sum([2**e for e in path])
        base[m] = v
    dp = [0] * (2**M)  # 制約の集合で出てくる最短 u->v パスで通るedgeの和集合の2進表記
    ans = 2**(N - 1)
    for S in range(1, 2**M):
        lenbit_s = len('{:b}'.format(S))
        dp[S] = dp[S - (1 << (lenbit_s - 1))] | base[lenbit_s - 1]
        cnt_s = count_bits(S)
        cnt_dp = count_bits(dp[S])
        ans += (-1)**(cnt_s % 2) * 2**(N - 1 - cnt_dp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

import sys
input = sys.stdin.readline

N = int(input())
edge = [tuple(map(int, input().split())) for _ in range(N - 1)]

M = int(input())
restriction = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

t = Tree(N, edge)
t.setroot(0)
t.heavylight_decomposition()

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

for i in range(M):
    u, v = restriction[i]
    for lt, rt in t.range_hld(u, v, 1):
        for j in range(lt, rt):
            white_node[i].add(j)

res = 0

for bit in range(2**M):
    cnt = 0
    det = set()
    for i in range(M):
        if (bit >> i) & 1:
            cnt += 1
            det |= white_node[i]

    if cnt % 2 == 0:
        res += 2**(N - 1 - len(det))
    else:
        res -= 2**(N - 1 - len(det))

print(res)

Submission status: Accepted

Solution code:


def resolve():
    def dfs(u, v, parent):
        if u == v:
            return True
        for (to, idx) in G[u]:
            if to == parent:
                continue
            if dfs(to, v, u):
                path.append(idx)
                return True
        return False

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

    path = []

    M = int(input())
    cons = [0]*M
    # 制約ごとに、白くなる辺を入れておく
    for i in range(M):
        u, v = map(lambda x: int(x) - 1, input().split())
        path = []
        dfs(u, v, -1)
        for idx in path:
            cons[i] |= 1<<idx

    # 包除原理
    ans = 0
    for bit in range(1<<M):
        eset = 0
        for i in range(M):
            if bit>>i & 1:
                eset |= cons[i]
        white = bin(eset).count("1") # 白くなるべき辺の数
        num = 1<<(N-1-white)
        if bin(bit).count("1") % 2 == 0:
            ans += num
        else:
            ans -= num
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#F - Tree and constraints
#メモリテスト
import itertools
from collections import defaultdict
N = int(input())
G = [[] for i in range(N+1)]
edge = defaultdict(int)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[(min(a, b), max(a, b))] = i+1
    G[a].append(b)
    G[b].append(a)
M = int(input())
que = [tuple(map(int, input().split())) for i in range(M)]
Data = [set([]) for i in range(M)]


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)


for i in range(M):
    s, g = que[i]
    visited = [False for i in range(N+1)]
    parent = [-1 for i in range(N+1)]
    dfs(s)
    now = g
    while parent[now] > 0:
        number = edge[(min(now, parent[now]), max(now, parent[now]))]
        Data[i].add(number)
        now = parent[now]
ans = 2**(N-1)
seq = [i for i in range(M)]
for i in range(1, M+1):
    # Mこからi+1こを選ぶ
    S = 0

    for v in itertools.combinations(seq, i):
        subset = set([])
        for x in v:
            subset = subset | Data[x]
        S += 2**(N-1-len(subset))
    ans -= (-1)**((i-1) % 2)*S
print(ans)

Submission status: Accepted

Solution code:
#F - Tree and constraints
import itertools
from collections import defaultdict
N = int(input())
G = [[] for i in range(N+1)]
edge = defaultdict(int)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[(min(a, b), max(a, b))] = i+1
    G[a].append(b)
    G[b].append(a)
M = int(input())
que = [tuple(map(int, input().split())) for i in range(M)]
Data = [set([]) for i in range(M)]


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)


for i in range(M):
    s, g = que[i]
    visited = [False for i in range(N+1)]
    parent = [-1 for i in range(N+1)]
    dfs(s)
    now = g
    while parent[now] > 0:
        number = edge[(min(now, parent[now]), max(now, parent[now]))]
        Data[i].add(number)
        now = parent[now]
ans = 2**(N-1)
seq = [i for i in range(M)]
for i in range(1, M+1):
    # Mこからi+1こを選ぶ
    S = 0
    subset = set([])
    for v in itertools.combinations(seq, i):
        subset.clear()
        for x in v:
            subset = subset | Data[x]
        S += 2**(N-1-len(subset))
    ans -= (-1)**((i-1) % 2)*S
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

def all_bit_count(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 = int(readline())
d = defaultdict(int)
cnt = 1

g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,0))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            mm = mi*100+ma
            if d[mm] == 0:
              d[mm] = cnt
              cnt += 1
            que.append((i,L|(1<<d[mm])))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = 0
    for k in j:
      K |= k
    l = all_bit_count(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Submission status: Accepted

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

n = int(readline())
g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)
  
m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,set()))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            que.append((i,L|{mi*100+ma}))
                     
import itertools
#print(c)
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = set()
    for k in j:
      K |= k
    l = len(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
    
m = int(input())
uvs = [None]*m
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uvs[i] = (u,v)
    
from queue import deque    
def bfs(start):
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    return seen

paths = [None]*m
for i,(u,v) in enumerate(uvs):
    seen = bfs(u)
    ss = set()
    z = v
    while z!=u:
        z1 = seen[z]
        ss.add(uv2e[z,z1])
        z = z1
    paths[i] = ss
    
ans = 0
def dfs(l, s):
    if len(l)==m:
        global ans
        val = pow(2, n-1-len(s)) * pow(-1, sum(l))
        ans += val
#         print(val, sum(l), ans)
        return
    l.append(0)
    dfs(l, s)
    l.pop()
    
    i = len(l)
    p = paths[i]
    l.append(1)
    dfs(l, s|p)
    l.pop()
    
dfs([], set())
# ans = pow(2,n-1) - ans
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1,u-1] = i
    
m = int(input())
uvs = [None]*m
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uvs[i] = (u,v)
    
from queue import deque    
def bfs(start):
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    return seen

paths = [None]*m
for i,(u,v) in enumerate(uvs):
    seen = bfs(u)
    ss = set()
    z = v
    while z!=u:
        z1 = seen[z]
        ss.add(uv2e[z,z1])
        z = z1
    paths[i] = ss
    
ans = 0
def dfs(l, s):
    if len(l)==m:
        global ans
        val = pow(2, n-1-len(s)) * pow(-1, sum(l))
        ans += val
#         print(val, sum(l), ans)
        return
    dfs(l + [0], s)
    
    i = len(l)
    p = paths[i]
    dfs(l + [1], s|p)
    
dfs([], set())
# ans = pow(2,n-1) - ans
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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 dfs(s, g):
    kouho = 0
    par = [(0, 0)] * (n + 1)
    stack = []
    stack.append(s)
    while stack:
        v = stack.pop()
        if v == g:
            break
        for u, i in graph[v]:
            if u == par[v][0]:
                continue
            par[u] = (v, i)
            stack.append(u)
    # 経路復元
    p = g
    q, i = par[p]
    while q > 0:
        kouho |= 1 << i
        p = q
        q, i = par[q]
    return kouho


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


sets = [0 for _ in range(m)]

for idx, (u, v) in enumerate(UV):
    sets[idx] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
    kumiawase = list(combinations(range(m), i))
    for kumi in kumiawase:
        temp = 0
        for j in range(i):
            temp |= sets[kumi[j]]
        num = popcnt(temp)
        ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append((b,i))
        G[b].append((a,i))
    
    between = [[set() for _ in range(N)] for _ in range(N)]
    for i in range(N):
        stack = [(i,[])]
        while stack:
            v,before = stack.pop()
            between[i][v] = set(before)
            for e,j in G[v]:
                if e == i or len(between[i][e]) >= 1:
                    continue
                between[i][e] = set(before + [j])
                stack.append((e,before + [j]))
            #print('before: ',before)
            #print('v :',v)
    
    #print(between)

    M = int(input())
    condition = [tuple(map(int,input().split())) for _ in range(M)]
    condition = [(a - 1,b - 1) for a,b in condition]
    
    ans = 0
    for bit in range(1<<M):
        ret = set()
        cnt = 0
        for i in range(M):
            if (bit>>i)&1:
                cnt += 1
                ret |= between[condition[i][0]][condition[i][1]]
        
        free = N - len(ret) - 1
        #print('free :',free)
        if cnt%2 == 0:
            ans += pow(2,free)
        else:
            ans -= pow(2,free)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列


    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        for i, (a, b) in enumerate([map(int, input().split()) for i in range(N-1)]):#木じゃない場合N-1をNに変える
            edgelist[a-1].append((b-1,i))#ノードの番号が0から始まる場合-1を消す
            edgelist[b-1].append((a-1,i))
        return edgelist
    edge=tree_init(N)
    M = int(input())
    ms= tuple(tuple(map(int, input().split())) for i in range(M))
    ways=[]

    for u,v in ms:
        u-=1;v-=1
        q=deque([(u,[])])
        visited=[False]*N
        while q:
            x=q.pop()#ここをpopleftにすると幅優先探索BFSになる
            #print(x)
            e,way=x
            if visited[e]:continue
            #print(way)
            if e==v:
                ways.append(set(way))
            visited[e]=True
            for ne, j in edge[e]:
                nw=copy(way)
                nw.append(j)
                q.append((ne,nw))
                
    tot=pow(2,N-1)
    for i in range(1,M+1):
        for ws in combinations(ways,i):
            ts=set()
            for w in ws:
                ts|=w
            # print(len(ts))
            tot+=(-1)**i*pow(2,N-1-len(ts))
    print(tot)
    #print(2**49-1)
if __name__ == "__main__":
    main()