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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    """
    余事象：Q1~QMのどれかを満たさないものの数を数える
    「Q1を満たさない」は数えやすい．ここから包除
    """
    N=I()
    adj=[[]for _ in range(N)]
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        
        #a<bにしておく
        if a>b:
            a,b=b,a
        adj[a].append(b)
        adj[b].append(a)
        dd[(a,b)]=1<<i#辺のid
        
    #popcount####################
    def popcount(x):
        '''xの立っているビット数をカウントする関数
        (xは64bit整数)'''

        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
        x = x + (x >> 8) # 16bitごと
        x = x + (x >> 16) # 32bitごと
        x = x + (x >> 32) # 64bitごと = 全部の合計
        return x & 0x0000007f
    
    
    #LCA-経路復元########################
    # N: 頂点数
    # G[v]: 頂点vの子頂点 (親頂点は含まない)


    def EulerTour(n, X, i0):
        # 隣接グラフXを消費しながら，親リストPを作りながら進む．
        # i0が根
        
        P = [-1] * n
        st = [~i0, i0]
        ct = -1
        ET = []
        ET1 = [0] * n#最初に出てくるとき
        ET2 = [0] * n#最後に出てくるとき
        DE = [0] * n
        de = -1
        while st:
            #頂点 i を見る
            
            i = st.pop()
            
            #帰り際の処理，ここを入れる場合，オイラーツアーの最後に「-1」がつくので注意
            if i < 0:
                #"""
                #↓ 戻りも数字を足す場合はこれを使う
                ct += 1
                # ↓ 戻りもETに入れる場合はこれを使う
                ET.append(P[~i])#notのnot
                #"""
                ET2[~i] = ct
                de -= 1
                continue
            
            #行きがけの処理
            if i >= 0:
                ET.append(i)
                ct += 1
                if ET1[i] == 0: ET1[i] = ct
                de += 1
                DE[i] = de
                
            for a in X[i][::-1]:
                if a != P[i]:
                    P[a] = i
                    for k in range(len(X[a])):
                        if X[a][k] == i:
                            del X[a][k]
                            break
                    st.append(~a)
                    st.append(a)
        return (ET, ET1, ET2, DE, P)

    # Euler Tour の構築
    S,F,Frev,depth,P=EulerTour(N,adj,0)
    """
    S:訪問順
    F:最初に出てくるとき(頂点の開始番号)
    Frev：最後に出てくるとき(頂点の終了番号)
    """

    # 存在しない範囲は深さが他よりも大きくなるようにする
    INF = (N, None)

    # LCAを計算するクエリの前計算
    M = 2*N
    M0 = 2**(M-1).bit_length()
    data = [INF]*(2*M0)
    for i, v in enumerate(S):
        data[M0-1+i] = (depth[v], i)
    for i in range(M0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])

    # LCAの計算 (generatorで最小値を求める)
    def _query(a, b):
        yield INF
        a += M0; b += M0
        while a < b:
            if b & 1:
                b -= 1
                yield data[b-1]
            if a & 1:
                yield data[a-1]
                a += 1
            a >>= 1; b >>= 1

    # LCAの計算 (外から呼び出す関数)
    def query(u, v):
        fu = F[u]; fv = F[v]
        if fu > fv:
            fu, fv = fv, fu
        return S[min(_query(fu, fv+1))[1]]
    
    def make_route(u,v):
        #使う辺の集合を50bit整数で返す，u,vからそれぞれlcaまで
        
        e=0
        lca=query(u,v)
        for i in range(2):
            if i==1:
                v=u
            while v!=lca:
                p=P[v]
                if p<v:
                    e+=dd[(p,v)]
                else:
                    e+=dd[(v,p)]
                v=p
            
        return e
    #########################

    M=I()
    U=[0]*M
    V=[0]*M
    
    E=[]
    
    for i in range(M):
        U[i],V[i]=MI()
        U[i]-=1
        V[i]-=1
        E.append(make_route(U[i],V[i]))
        #print(i,bin(E[i]))
    
    ans=0
    for i in range(pow(2,M)):#使う条件の集合
        e=0#白にすべきところ
        for j in range(M):#j個目の制約に注目
            if (i>>j)&1:
                e2=E[j]
                e=e|e2#白く塗るべきところが増えていく
                
        temp=pow(2,(N-1)-popcount(e))#bitが0のところは各2通りなので
        #print(bin(i),bin(e),temp)
        if popcount(i)%2==0:#包除原理，立っているbitが偶数個ならプラス
            ans+=temp
        else:
            ans-=temp
            
    print(ans)
            
                
                
            
        
    

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

from collections import defaultdict
from collections import deque
import math


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


class LCA(object):
    def __init__(self, g: Graph, root: int = 0):
        self.construct(g, root)

    def construct(self, g: Graph, root=0):
        """
        木gにおいて、頂点u, vのLCA(Lowest Common Ancestor)を求める
        g: 木。無向グラフとして与える。
        u, v:頂点
        root: 根
        元: https://tjkendev.github.io/procon-library/python/graph/lca-doubling.html
        """
        self.N = g.N
        self.LN = len(bin(g.N).lstrip("-0b"))

        # 各頂点の親 parと各頂点の深さdepthを求める
        par = [INF]*self.N
        self.depth = [INF]*self.N

        que = deque()
        que.append([root, 0, None])
        while len(que) > 0:
            curr, dep, pre = que.popleft()
            par[curr] = pre
            self.depth[curr] = dep
            for n, w in g.E[curr]:
                if n != pre:
                    que.append([n, dep+w, curr])

        # 祖先 ancの構築
        # anc[i][j]は頂点jの2**i個上の祖先を示す
        self.anc = [par]

        for i in range(self.LN):
            buf = [None]*self.N
            for j in range(self.N):
                if self.anc[i][j] == None:
                    continue
                buf[j] = self.anc[i][self.anc[i][j]]
            self.anc.append(buf)

        return

    def query(self, u: int, v: int):
        # 共通祖先を求める
        dd = self.depth[v] - self.depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd

        for k in range(self.LN):
            if dd & 1:
                v = self.anc[k][v]
            dd >>= 1

        if u == v:
            return u

        for k in range(self.LN-1, -1, -1):
            pu = self.anc[k][u]
            pv = self.anc[k][v]
            if pu != pv:
                u = pu
                v = pv

        return self.anc[0][u]


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


def solve(N: int, a: "List[int]", b: "List[int]",
          M: int, u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for X, Y in zip(a, b):
        g.add_edge(X-1, Y-1)
    # LCAを使う
    lca = LCA(g)

    # 条件を与える頂点を結ぶパスをbit列で与える
    paths = []
    for j in range(M):
        path = 0
        a1 = u[j]-1
        a2 = v[j]-1
        p = lca.query(a1, a2)
        while a1 != p:
            path |= 1 << (a1-1)
            a1 = lca.anc[0][a1]
        while a2 != p:
            path |= 1 << (a2-1)
            a2 = lca.anc[0][a2]
        paths.append(path)
    # print([bin(p) for p in paths])

    ans = 2**(N-1)
    for p in range(1, 1 << M):
        spider_net = 0
        strp = bin(p).lstrip("0b")
        # print("パターン", strp)
        for i, c in enumerate(strp[::-1]):
            if c == "1":
                spider_net |= paths[i]
        C = bit_sum(spider_net)
        # print(C, bin(spider_net))
        if bit_sum(p) % 2 == 1:
            ans -= 2**(N-1-C)
        else:
            ans += 2**(N-1-C)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]"
    v = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, b, M, u, v)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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: Accepted

Solution code:
import sys
from itertools import combinations 
from collections import defaultdict
input = sys.stdin.readline
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)]

g = defaultdict(list)
pathnum = {}
for n,(a,b) in enumerate(ab):
    g[a].append(b)
    g[b].append(a)
    a,b = sorted([a,b])
    pathnum[(a,b)] = n

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    vtour = []
    etour = []
    depth = [-1]*(n+1)
    parent = [False]*(n+1)
    visited = [False]*(n+1)
    def dfs(v,d):
        depth[v] = d
        visited[v] = True
        ls[v] = len(vtour)
        vtour.append(v)
        etour.append(v)
        for nv in g[v]:
            if not visited[nv]:
                parent[nv] = v
                dfs(nv,d+1)
        rs[v] = len(vtour)
        etour.append(-v)
        vtour.append(parent[v])
    dfs(s,0)
    return ls,rs,etour,vtour,parent,depth

ls,rs,etour,vtour,parent,depth = eulerTour(g,1)
paths = []
depthind = [depth[v] for v in vtour]

for u,v in uv:
    l,r = ls[u],ls[v]
    l,r = (l,r) if l < r else (r,l)
    lcaind = depthind[l:r].index(min(depthind[l:r]))
    lca = vtour[l+lcaind]
    lpath = []
    x = u
    while x != lca:
        lpath.append(pathnum[tuple(sorted((x,parent[x])))])
        x = parent[x]
    rpath = []
    x = v
    while x != lca:
        rpath.append(pathnum[tuple(sorted((x,parent[x])))])
        x = parent[x]
    path = set(lpath + rpath)
    h = sum([1<<i for i in path])
    paths.append(h)
    
ans = 2**(N-1)

memo = {1<<i:paths[i] for i in range(M)}
memo[0] = 0
for i in range(1,M+1):
    for vs in combinations(list(range(M)),i):
        sign = i % 2
        h = sum([1<<i for i in vs])
        ph = h ^ (1<<vs[-1])
        sect = memo[ph] | paths[vs[-1]]
        memo[h] = sect
        num = N-1 - str(bin(sect)).count('1')
        ans += (-1)**sign * (2**num)

print(ans)

Submission status: Accepted

Solution code:
# ABC152F

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
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = 0
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es |= 1<<uv2e[u,seen[u]]
        if seen[u]==start:
            break
        u = seen[u]
    return es

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
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

# def dfs(ind, s, ans):
#     if len(ind)==m:
#         if True in ind:
#             tmp = 0
#             for i in range(n-1):
#                 tmp += (s & 1<<i)>0
#             ans += 2**(n-1-tmp) * (-1)**((sum(ind)+1)%2)
#         return ans
#     ans = dfs(ind + [True], s | paths[len(ind)], ans)
#     ans = dfs(ind + [False], s, ans)
#     return ans
        
def bitlen(b):
    tmp = 0
    for i in range(n-1):
        tmp += (b&1<<i)>0
    return tmp
for ind in itertools.product(*[(False, True) for _ in range(m)]):
    num = sum(ind)+1
    if num==1:
        continue
    c = 2**(n - 1 - bitlen(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), 0)))
    ans += (-1)**num * c
# ans = dfs([], 0, 0)
print(2**(n-1) - ans)

Submission status: Accepted

Solution code:
# ABC152F

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
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = 0
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es |= 1<<uv2e[u,seen[u]]
        if seen[u]==start:
            break
        u = seen[u]
    return es

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
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            tmp = 0
            for i in range(n-1):
                tmp += (s & 1<<i)>0
            ans += 2**(n-1-tmp) * (-1)**((sum(ind)+1)%2)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], 0, 0)
print(2**(n-1) - ans)

Submission status: Accepted

Solution code:
# ABC152F

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
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-len(s)) * (-1)**((sum(ind)+1)%2)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], set(), 0)
print(2**(n-1) - ans)

Submission status: Accepted

Solution code:
# ABC152F

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
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-len(s)) * (-1)**(sum(ind)+1)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], set(), 0)
print(2**(n-1) - ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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


def dfs(v, v_p, target):
    if v == target:
        return True, 0

    for v_next, edge_idx in graph[v]:
        if v_next == v_p:
            continue
        is_target, path = dfs(v_next, v, target)
        if is_target:
            return is_target, path | (1 << edge_idx)
    return False, 0


m = int(input())
cond = []
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    _, path = dfs(u, -1, v)
    # print(u, v, bin(path))
    cond.append((u, v, path))

ans = 1 << (n - 1)
for bit in range(1, 1 << m):
    l = 0
    path = 0
    for i, (u, v, path_i) in enumerate(cond):
        if (bit >> i) & 1:
            l += 1
            path = path | path_i

    c = n - 1 - bin(path).count('1')
    ans += ((-1)**(l % 2)) * (1 << c)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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


def dfs(v, v_p, target):
    if v == target:
        return True, 0

    path = 0
    for v_next, edge_idx in graph[v]:
        if v_next == v_p:
            continue
        is_target, path = dfs(v_next, v, target)
        if is_target:
            return is_target, path | (1 << edge_idx)
    return False, 0


m = int(input())
cond = []
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    _, path = dfs(u, -1, v)
    # print(u, v, bin(path))
    cond.append((u, v, path))

ans = 1 << (n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    path = 0
    for i, (u, v, path_i) in enumerate(cond):
        if (bit >> i) & 1:
            l += 1
            path = path | path_i

    # print(bin(bit), cnt)
    c = n - 1 - bin(path).count('1')
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**(l % 2)) * (1 << c)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()

graph = [[] for _ in range(N)]
edges = []
 
for _ in range(N - 1):
  a, b = inputIL()
  edges.append((a-1, b-1))
  
for a, b in edges:
  graph[a].append(b)
  graph[b].append(a)
  
  
M = inputI()
m = inputILL(M)

prv = [None for i in range(N)]

prv[0] = -1

q = deque([0])

while q:
  u = q.popleft()
  for v in graph[u]:
    if prv[v] == None:
      prv[v] = u
      q.append(v)

to_root = []

for i in range(N):
  s = 0
  now = i
  while now!=0:
    s += pow(2,now)
    now = prv[now]
  to_root.append(s)

  
ans = 0
for k in range(pow(2,M)):
  J = []
  for i in range(M):
    if k>>i & 1:
      J.append(m[i])
  mask = 0
  for u,v in J:
    mask |= to_root[u-1]^to_root[v-1]
  ##########
  count = 0
  while mask:
    mask &= mask -1
    count += 1
  ##########
  c = 0
  while k:
    k &= k -1
    c += 1
  sign = 1
  if c%2 == 1:
    sign = -1
  ###########
  ans += sign * pow(2,N-1-count)

print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7; INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.prev[i] = v
					self.Q.put(i)
					self.visit[i] = "Yes"

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	G = Graph()
	D = defaultdict(int)
	for i in range(N - 1):
		a, b = sorted(getlist())
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		D[10000 * a + b] = i

	M = int(input())
	MbitTable = [0] * (N - 1)
	for i in range(M):
		u, v = getlist()
		u -= 1; v -= 1
		BF = BFS(G, u, N)
		prev = BF.prev
		node = v
		edge = []
		while prev[node] != None:
			a, b = sorted([node, prev[node]])
			edgenum = D[10000 * a + b]
			edge.append(edgenum)
			node = prev[node]

		for j in edge:
			MbitTable[j] += 2 ** i

	DP = [[0] * (2 ** M) for i in range(N)]
	DP[0][0] = 1
	for i in range(N - 1):
		for j in range(2 ** M):
			DP[i + 1][j] += DP[i][j]
			DP[i + 1][j | MbitTable[i]] += DP[i][j]

	print(DP[-1][-1])

if __name__ == '__main__':
	main()