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:
N=int(input())
edge={i:[] for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    edge[a].append((b,i))
    edge[b].append((a,i))

parent={i:-1 for i in range(1,N+1)}
depth={i:-1 for i in range(1,N+1)}
parent[1]=(0,-1)
depth[1]=0
q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for b,i in edge[x]:
            if parent[b]==-1:
                parent[b]=(x,i)
                depth[b]=depth[x]+1
                sub.add(b)

        if not q:
            q=sub
            sub=set([])
            break

M=int(input())
condition=[[] for i in range(0,M)]
for i in range(0,M):
    u,v=map(int,input().split())
    ans=set([])
    while depth[u]!=depth[v]:
        if depth[u]>depth[v]:
            U,j=parent[u]
            ans.add(j)
            u=U
        else:
            V,j=parent[v]
            ans.add(j)
            v=V

    while u!=v:
        U,j=parent[u]
        ans.add(j)
        u=U
        V,j=parent[v]
        ans.add(j)
        v=V
    con=0
    for j in ans:
        con+=2**j
    condition[i]=con

ans=2**(N-1)
ban=0
for i in range(1,2**M):
    num=bin(i).count('1')
    s=0
    for j in range(0,M):
        if i>>j &1==1:
            s=s|condition[j]


    n=bin(s).count('1')
    if num%2==1:
        ban+=2**(N-1-n)
    else:
        ban-=2**(N-1-n)

print(ans-ban)

Submission status: Accepted

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

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

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

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

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    edge_to_idx = {}
    for i in range(n - 1):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        E[u].append(v)
        E[v].append(u)
        edge_to_idx[u, v] = edge_to_idx[v, u] = i

    def path(source, target):
        par = [-1] * n
        stack = [(source, -1)]
        while stack:
            v, p = stack.pop()
            for nv in E[v]:
                if nv == p:
                    continue
                par[nv] = v
                stack.append((nv, v))
        res = 0
        while target != source:
            res |= 1 << edge_to_idx[target, par[target]]
            target = par[target]
        return res

    m = int(input())
    constraints = [None] * m
    for i in range(m):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        constraints[i] = path(u, v)

    res = 1 << (n - 1)
    # inc - exc principle
    for U in range(1, 1 << m):
        coef = 1 if bin(U).count('1') & 1 else -1
        binary = 0
        for i in range(m):
            if (U >> i) & 1:
                binary |= constraints[i]
        cnt = (n - 1) - bin(binary).count('1')
        res -= coef * (1 << cnt)

    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    edge_to_idx = {}
    for i in range(n - 1):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        E[u].append(v)
        E[v].append(u)
        edge_to_idx[u, v] = edge_to_idx[v, u] = i

    def path(v, p, target):
        # base case
        if v == target:
            return 1 << edge_to_idx[v, p]
        res = 0
        for nv in E[v]:
            if nv == p:
                continue
            res |= path(nv, v, target)
        if res > 0 and p != -1:
            res |= 1 << edge_to_idx[v, p]
        return res

    m = int(input())
    constraints = [None] * m
    for i in range(m):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        constraints[i] = path(u, -1, v)

    res = 1 << (n - 1)
    # inc - exc principle
    for U in range(1, 1 << m):
        coef = 1 if bin(U).count('1') & 1 else -1
        binary = 0
        for i in range(m):
            if (U >> i) & 1:
                binary |= constraints[i]
        cnt = (n - 1) - bin(binary).count('1')
        res -= coef * (1 << cnt)

    print(res)
resolve()

Submission status: Accepted

Solution code:
# https://drken1215.hatenablog.com/entry/2020/01/26/164200
# bit_pathの参考にした
# https://atcoder.jp/contests/abc152/submissions/9619555
# popcnt

def main():
    from collections import namedtuple
    from functools import reduce
    from itertools import combinations
    from operator import or_

    Edge = namedtuple('Edge', 'to edge_id')

    def bit_path(curr, goal, par=-1):
        if curr == goal:
            return 0
        for e in g[curr]:
            if e.to == par: continue
            res = bit_path(curr=e.to, goal=goal, par=curr)
            if ~res:  # -1以外
                return res | (1 << e.edge_id)
        return -1

    def popcnt(n):
        """https://atcoder.jp/contests/abc152/submissions/9619555"""
        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())

    g = tuple(set() for _ in range(N))
    for edge_id in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(Edge(to=b, edge_id=edge_id))
        g[b].add(Edge(to=a, edge_id=edge_id))

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    ans = 1 << (N - 1)
    for k in range(1, M + 1):
        for comb in combinations(cons, r=k):
            b = reduce(or_, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - popcnt(b)))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://drken1215.hatenablog.com/entry/2020/01/26/164200
# bit_pathの参考にした

def main():
    from collections import namedtuple
    from functools import reduce
    from itertools import combinations
    from operator import or_

    Edge = namedtuple('Edge', 'to edge_id')

    def bit_path(curr, goal, par=-1):
        if curr == goal:
            return 0
        for e in g[curr]:
            if e.to == par: continue
            res = bit_path(curr=e.to, goal=goal, par=curr)
            if ~res:  # -1以外
                return res | (1 << e.edge_id)
        return -1

    N = int(input())

    g = tuple(set() for _ in range(N))
    for edge_id in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(Edge(to=b, edge_id=edge_id))
        g[b].add(Edge(to=a, edge_id=edge_id))

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    ans = 1 << (N - 1)
    for k in range(1, M + 1):
        for comb in combinations(cons, r=k):
            b = reduce(or_, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - bin(b).count('1')))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def examA():
    N = I()
    L = LI()
    L.sort()
    if sum(L)<=L[-1]*2:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, M = LI()
    A = [LI()for _ in range(N)]
    A.sort(key=lambda x:x[0])
    ans = 0
    for a,b in A:
        if M<=b:
            ans += a*M
            break
        ans += a*b
        M -= b
    print(ans)
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    D = defaultdict(int)
    for s in S:
        cur = []
        for i,j in Counter(s).items():
            cur.append((i,j))
        #print(cur)
        cur.sort()
        cur = tuple(cur)
        D[cur] += 1
    ans = 0
    for d in D.values():
        ans += (d-1)*d//2
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+A[i]
    ans = 0
    for i in range(N):
        l = i-1; r = N
        if S[-1]-S[i]<K:
            break
        while(r-l>1):
            now = (l+r)//2
            if S[now]-S[i]<K:
                l = now
            else:
                r = now
        #print(i,r)
        ans += (N-r+1)
    print(ans)
    return

def examE():
    # 区間加算、上書き、一点取得
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret

    N, D, A = LI()
    X = [LI()for _ in range(N)]
    X.sort()
    L = [0]*N
    for i in range(N):
        L[i] = X[i][0]
    S = SegmentTree(N,0,lambda a, b: a+b)
    ans = 0
    for i,[x,h] in enumerate(X):
        H = h - S.query(i)
        if H<=0:
            continue
        ne = bisect.bisect_right(L,x+2*D)
        #print(ne)
        need = (H-1)//A + 1
        S.update(i,ne,need*A)
        ans += need
    print(ans)
    return

def examF():
    N = I()
    V = [[]for _ in range(N)]
    Num_edge = {}
    for i in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
        Num_edge[(a,b)] = i
        Num_edge[(b,a)] = i
    def dfs(S,s,p,g):
        now = s
        neS = []
        if now==g:
            return S
        for ne in V[now]:
            if ne==p:
                continue
            neS = dfs(S+(1<<Num_edge[(now,ne)]),ne,now,g)
            if neS:
                return neS
        return
    M = I()
    Q = [0]*M

    for i in range(M):
        a, b = LI()
        a -= 1; b -= 1
        Q[i] = dfs(0,a,-1,b)
    #print(Q)
    ans = pow(2,N-1)
    loop = 2**M
    for i in range(1,loop):
        cur = 0
        num = 0
        for k in range(M):
            if i&(1<<k)>0:
                num += 1
                cur |= Q[k]
        #print(i,cur)
        if num%2==1:
            ans -= 1 << (N - 1 - bin(cur).count("1"))
        else:
            ans += 1 << (N - 1 - bin(cur).count("1"))
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
# 解説AC
from collections import deque

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

def bfs(s:int, g:int):
    """ 始点sから終点gまでのパスを求める """
    in_edge = [-1] * N
    par = [-1] * N
    flag = False # 終点到着フラグ
    
    que = deque([s])
    while que:
        v = que.popleft()
        for w, n in edge[v]:
            if w == par[v]: continue
            in_edge[w] = n
            par[w] = v
            if w == g:
                flag = True
                break
            que.append(w)
        if flag: break
    path = 0
    cur = g
    while in_edge[cur] >= 0:
        path |= 1 << in_edge[cur]
        cur = par[cur]
    return path


M = int(input())
path = [0] * M # 各制約で使用するパス
for i in range(M):
    u,v = map(int, input().split())
    path[i] = bfs(u - 1, v - 1)

ans = 0
# 包除原理
for bit in range(1 << M):
    val = 0
    for i in range(M):
        if (bit >> i) & 1:
            val |= path[i]
    if bin(bit).count("1") % 2 == 0:
        ans += 1 << (N - 1 - bin(val).count("1"))
    else:
        ans -= 1 << (N - 1 - bin(val).count("1"))

print(ans)

Submission status: Accepted

Solution code:

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def main():
    import sys
    import collections
    input = sys.stdin.readline
    N = int(input())
    G = [[-1]*N for i in range(N)]

    ans = 2**(N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = i
        G[b][a] = i
    ans = 0
    g = [[0]*N for i in range(N)]
    for i in range(N):
        q = collections.deque()
        q.append((i, 0))
        r = [True]*N
        r[i] = False
        while(q):
            x, s = q.popleft()
            for y in range(N):
                if G[x][y] >= 0 and r[y]:
                    g[i][y] = s | 1 << G[x][y]
                    q.append((y, g[i][y]))
                    r[y] = False
    M = int(input())
    s = [0 for i in range(M)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1

        s[i] = g[u][v]

    # print(s)
    for i in range(2**M):
        tmp = 2**(N-1) - 1
        c = 0
        for j in range(M):
            if (i >> j) % 2 == 1:
                tmp &= ~s[j]
                c += 1
        ans += ((-1)**(c))*(1 << popcount(tmp))

    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import deque
def solve(s, t):
    par = {}
    par[s] = -1
    q = deque([s])
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if nxt_v in par:
                continue
            else:
                q.append(nxt_v)
                par[nxt_v] = v
    res = []
    while True:
        if par[t] != -1:
            res.append(edge[min(t, par[t]), max(t, par[t])])
            t = par[t]
        else:
            return res
    
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
const = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
edge = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    edge[min(a, b), max(a, b)] = i
    tree[a].append(b)
    tree[b].append(a)
    
bit_v = [0] * m
for i in range(m):
    s, t = const[i]
    s -= 1
    t -= 1
    bit_state = 0
    for mask in solve(s, t):
        bit_state |= (1 << mask)
    bit_v[i] = bit_state

ans = 0
for bit_state in range(1, 1 << m):
    bit_cnt = bin(bit_state).count("1")
    mask = 0
    for i in range(m):
        if bit_state & (1 << i):
            mask |= bit_v[i]
    if bit_cnt % 2 == 0:
        ans -= 2 ** (n - 1 - bin(mask).count("1"))
    else:
        ans += 2 ** (n - 1 - bin(mask).count("1"))
print(2 ** (n - 1) - ans)

Submission status: Accepted

Solution code:
from itertools import combinations

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
m = int(input())
uv = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
ids = [[-1] * n for _ in range(n)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    ids[a][b] = i
    ids[b][a] = i


def dfs(s, g):
    d = [-1] * n
    d[s] = 0
    p = [-1] * n
    stack = [s]

    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    v = g
    ret = 0
    while v != s:
        i = ids[v][p[v]]
        ret += 1 << i
        v = p[v]

    return ret


def bin_count(tpl):
    sm_or = 0
    for e in tpl:
        sm_or |= e

    return bin(sm_or).count("1")


path = [dfs(u - 1, v - 1) for u, v in uv]
ex = 0
for i in range(1, m + 1):
    for tpl in combinations(path, i):
        ex += pow(2, n - 1 - bin_count(tpl)) * (-1) ** (i % 2 + 1)

ans = pow(2, n - 1) - ex
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    m=int(input())
    C=[]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        C.append((u,v))
    
    def normalized(u,v):
        return (min(u,v),max(u,v))
    def findpath(u,v,visited=None):
        if visited is None:
            visited=set()
        if u==v:
            return set()
        if u in visited:
            return None
        visited.add(u)
        for x in Edges[u]:
            P=findpath(x,v,visited)
            if P is not None:
                P.add(normalized(u,x))
                return P
    def set_path(Pairs,Paths):
        if len(Pairs)<=1:
            yield ((Pairs[0],),Paths[Pairs[0]])
            yield ((),set())
        else:
            for S,P in set_path(Pairs[1:],Paths):
                yield ((Pairs[0],)+S,P|Paths[Pairs[0]])
                yield (S,P)
    
    Paths={}
    for u,v in C:
        Paths[(u,v)]=findpath(u,v)
    ans=pow(2,(n-1))
    for S,P in set_path(C,Paths):
        l=len(S)
        if l<=0:
            continue
        c=pow(2,(n-1)-len(P))
        flag=1 if l%2==0 else -1
        ans+=flag*c
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def dfs(p, g, pre=-1):
        for e in edg[p]:
            if e == pre: continue
            if e == g:
                return [d[(p, e)]]
            tmp = dfs(e, g, p)
            if tmp:
                return tmp + [d[(p, e)]]
        return False

    n = II()
    edg = [[] for i in range(n)]
    t = 0
    ab = defaultdict(int)
    d = defaultdict(int)
    for _ in range(n - 1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
        d[(a, b)] = t
        d[(b, a)] = t
        t += 1
    m = II()
    path = [0] * m 
    uv = LIR_(m)
    for i, uvi in enumerate(uv):
        u, v = uvi
        pat = dfs(u,v)
        for p in pat:
            path[i] |= 1 << p
    ans = 1 << (n - 1)
    for mask in range(1, 1 << m):
        tmp = 0
        t = 0
        for i in range(m):
            if mask & (1 << i):
                t += 1
                tmp = tmp | path[i]
        x = 0
        while tmp:  
            x += tmp & 1
            tmp >>=1
        ans += (1 << (n - x - 1)) * (-1) ** t
    print(ans)


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import *

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 i in range(N)]
edge_id = defaultdict(lambda : -1)
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)
    edge_id[(a, b)] = edge_id[(b, a)] = i
path = defaultdict(lambda : -1)

def set_path(r, v, path_):
    visited[v] = 1
    path[(r, v)] = path_
    for u in edges[v]:
        if visited[u] == 0:
            set_path(r, u, path_ | (1 << edge_id[(v, u)]))

for i in range(N):
    visited = [0] * N
    set_path(i, i, 0)
M = int(input())
uv = [list(map(lambda x: int(x)-1, input().split())) for i in range(M)]
ans = pow(2, N-1)
for i in range(1, 1 << M):
    all_path = 0
    for j, (u, v) in enumerate(uv):
        if i & (1 << j):
            all_path |= path[(u, v)]
    if popcnt(i) & 1:
        ans -= pow(2, N-1-popcnt(all_path))
    else:
        ans += pow(2, N-1-popcnt(all_path))
print(ans)

Submission status: Accepted

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

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = bin(i).count("1") % 2
    ans += (-1)**cnt * 2**(n-1-bin(s).count("1"))
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def DFS(graph,root,parent):
  dist = [-1]*(n+1)
  dist[root] = 0
  stack = [root]
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        parent[y] = x
        dist[y] = dist[x]+1
        stack.append(y)
  return dist

#親のリスト、頂点v、kが与えられたときに「vのk個上の祖先」を見る
class Doubling:
  def __init__(self,graph,root):
    self.root = root
    n = len(graph)-1
    self.ancestor_ls = [[0]*(n+1)]
    self.distance = DFS(graph,root,self.ancestor_ls[0])
    self.bitn = n.bit_length()
    for i in range(1,self.bitn+1):
      ancestor_ls_app = [0]*(n+1)
      for j in range(1,n+1):
        ancestor_ls_app[j] = self.ancestor_ls[i-1][self.ancestor_ls[i-1][j]]
      self.ancestor_ls.append(ancestor_ls_app)
  
  def dist(self):
    return self.distance
  
  def parent(self):
    return self.ancestor_ls[0]

  def ancestor(self,v,depth):
    if depth == 0:
      return v
    if n<depth:
      return self.root
    ret = v
    for i in range(self.bitn):
      if depth&1<<i:
        ret = self.ancestor_ls[i][ret]
    return ret
  
  def LCA(self,u,v):
    if self.distance[u]<self.distance[v]:
      u,v = v,u
    dif = self.distance[u]-self.distance[v]
    w = self.ancestor(u,dif)
    if w == v:
      return v
    for i in range(self.bitn,-1,-1):
      if self.ancestor_ls[i][w] != self.ancestor_ls[i][v]:
        w,v = self.ancestor_ls[i][w],self.ancestor_ls[i][v]
    return self.ancestor_ls[0][v]

import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)

sol = Doubling(graph,1)
pls = sol.parent()

m = int(input())
cons = [0 for i in range(m)]
for i in range(m):
  u,v = map(int,input().split())
  lca = sol.LCA(u,v)
  while u != lca:
    cons[i] |= 1<<u
    u = pls[u]
  while v != lca:
    cons[i] |= 1<<v
    v = pls[v]
ans = 0
for i in range(2**m):
  x = 0
  for j in range(m):
    if i & 1<<j:
      x |= cons[j]
  bcnt = 0
  for j in range(n+1):
    if x & 1<<j:
      bcnt += 1
  if bin(i).count("1")%2 == 1:
    ans -= 2**(n-1-bcnt)
  else:
    ans += 2**(n-1-bcnt)
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    
    root = 0
    q = []
    q.append(root)
    pre = [-1]*N
    visited = [False]*N
    while q:
        v = q.pop() 
        visited[v] = True
        for to in edge[v]:
            if visited[to]:
                continue
            pre[to] = v
            q.append(to)
    
    path = [] #パスに含まれる辺(根に向かう方で保存)
    constraint = []
    M=I()
    for i in range(M):
        a,b = MI_()
        constraint.append((a,b))

        
        root_path_a = 1<<a
        root_path_b = 1<<b
        
        while a!=root:
            root_path_a |= 1<<pre[a]
            a = pre[a]
        while b!=root:
            root_path_b |= 1<<pre[b]
            b = pre[b]
        path.append(root_path_a ^ root_path_b) #LCAまでのみ
        if not path[-1]>>a&1:
            path[-1] |= 1<<a
        if not path[-1]>>b&1:
            path[-1] |= 1<<b
    

    ans = 0
    for mask in range(1<<M):
        builtin_count = 0
        U = 0 #pathに含まれる辺
        for i in range(M):
            if mask>>i&1:
                builtin_count += 1
                U |= path[i]
        edge_cnt = max(0,bin(U).count("1")-1)
        if builtin_count&1:
            ans -= 1<<(N-1-edge_cnt)
        else:
            ans += 1<<(N-1-edge_cnt)
    print(ans)



if __name__ == '__main__':
    main()