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:

"""
20個しかないので包除原理？
使う、使わないで 2**20通り

答え = 2**N - 1満たさない + 2つ満たさない - 3つ満たさない…
で表される

各場合はいずれかのパスに属す点以外は自由に塗れる
各パス上の点をbitで管理
黒に塗ってはいけない点のかずをあぶりだす

計算量は 2**20

"""
from collections import deque

N = int(input())

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1
    c = N+i

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []
    dic[c] = []

    dic[a].append(c)
    dic[b].append(c)
    dic[c].append(a)
    dic[c].append(b)

M = int(input())
bitlis = []

for loop in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1
    
    bits = [0] * N + [2**i for i in range(N-1)]
    dis = [float("inf")] * (2*N-1)
    dis[u] = 0

    q = deque([u])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:
            if dis[nex] > dis[now] + 1:
                dis[nex] = dis[now] + 1
                bits[nex] += bits[now]
                q.append(nex)

    bitlis.append(bits[v])

#print (bitlis)
uselis = [0] * (M+1)

for use in range(2**M):

    white = 0
    usenum = 0
    for i in range(M):
        if use & (2**i) > 0:
            white |= bitlis[i]
            usenum += 1

    able = N-1
    ws = format(white,"b")
    for i in ws:
        if i == "1":
            able -= 1

    uselis[usenum] += 2 ** able

#print (uselis)
ans = 2 ** (N-1)

for i in range(M):

    i += 1

    if i % 2 == 1:
        ans -= uselis[i]
    else:
        ans += uselis[i]

print (ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,g,p):
    global tmp
    if s == g:
        tmp = []
        return True
    for (v,i) in edge[s]:
        if v == p:
            continue
        if dfs(v,g,s):
            tmp.append(i)
            return True
    return False

n = I()
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    edge[a].append((b,i))
    edge[b].append((a,i))

m = I()
lst = []
tmp = []
for _ in range(m):
    u,v = LI()
    u -= 1
    v -= 1
    dfs(u,v,-1)
    lst.append(tmp)

"""m個の制約がどの辺を通るかbitで管理"""
e = [0]*m
for i in range(m):
    x = 0
    for j in lst[i]:
        x |= 1<<j
    e[i] = x

"""包除原理"""
ans = 0
for i in range(1<<m):
    black = 0 #制約の通る辺をbitで管理
    cnt = 0 #使う制約の個数
    """どの制約を使うか"""
    for j in range(m):
        if i>>j & 1:
            cnt += 1
            black |= e[j]

    cnt2 = 0 #制約内の辺の本数
    for j in range(n-1):
        if black >> j & 1:
            cnt2 += 1
    if cnt % 2: #制約奇数個の場合
        ans -= 1<<(n-1-cnt2) #-2**((n-1本の辺)-(制約内の辺の本数))
    else:
        ans += 1<<(n-1-cnt2) #+2**((n-1本の辺)-(制約内の辺の本数))
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

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

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
Cond=[0]*(2**m)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  Cond[i]=Cond[i^(i&(-i))]|passing[len(bin(i&(-i)))-3]
  cond_ct=popcount(Cond[i]) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n-1)]
m = I()
uv = [LI() for _ in range(m)]

edge = [[] for i in range(n)]
lst = [[None]*n for i in range(n)]
cnt = 0
for i,[a,b] in enumerate(ab):
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    lst[a-1][b-1] = i
    lst[b-1][a-1] = i

L = []
for u,v in uv:
    stack = deque()
    stack.append(u-1)
    flg = [True]*n
    par = [None]*n
    par[u-1] = -1
    while stack:
        x = stack.pop()
        if x == v-1:
            break
        flg[x] = False
        for y in edge[x]:
            if flg[y]:
                par[y] = x
                stack.append(y)
    tmp = v-1
    tmp2 = []
    while 1:
        if par[tmp] == -1:
            break
        tmp2.append(lst[tmp][par[tmp]])
        tmp = par[tmp]
    tmp2.sort()
    L.append(tmp2)

e = [0]*m
for i in range(m):
    x = 0
    for j in L[i]:
        x |= 1<<j
    e[i] = x

ans = 0
for i in range(1<<m):
    black = 0
    cnt = 0
    for j in range(m):
        if (i>>j & 1):
            cnt += 1
            black |= e[j]
    cnt2 = 0
    for j in range(n-1):
        if (black>>j & 1):
            cnt2 += 1
    if cnt % 2:
        ans -= 1<<(n-1-cnt2)
    else:
        ans += 1<<(n-1-cnt2)
print(ans)

Submission status: Accepted

Solution code:
import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]


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


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0
for i in range(1, 2**M):
    tmp = 2**(N-1) - 1
    for j in range(M):
        if (i >> j) % 2 == 1:
            u, v = uv[j]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
    ans2 += ((-1)**(popcount(i)-1)) * (1 << popcount(tmp))
    # print(ans2, i)
print(ans-ans2)

Submission status: Accepted

Solution code:
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class DoublingLCA:
    """
    LCA ダブリング版
    初期化 O(NlogN)、クエリ O(logN)
    """

    def __init__(self, graph, max_v, root):
        """
        :param list of (list of int) graph:
        :param int max_v:
        :param int root:
        """
        self.graph = graph
        self.size = max_v + 1
        self.root = root

        # AtCoder の PyPy 2.4.0 では math.log2 が使えない
        self.MAX_LOG_V = math.floor(math.log(self.size, 2)) + 1
        # depths[v]: v の root からの距離
        self.depths = [-1] * self.size
        # parents[k][v]: 親に 2^k たどった頂点
        self.parents = [[-1] * self.size for _ in range(self.MAX_LOG_V)]

        self._init()

    def _init(self):
        # depths と parents[0] を初期化
        seen = [False] * self.size
        stack = [(self.root, 0, -1)]
        while stack:
            v, d, par = stack.pop()
            self.parents[0][v] = par
            self.depths[v] = d
            seen[v] = True
            for u in self.graph[v]:
                if not seen[u]:
                    stack.append((u, d + 1, v))

        # 各 parents を初期化
        for k in range(self.MAX_LOG_V - 1):
            for v in range(self.size):
                if self.parents[k][v] < 0:
                    # 親がなければ -1
                    self.parents[k + 1][v] = -1
                else:
                    self.parents[k + 1][v] = self.parents[k][self.parents[k][v]]

    def lca(self, u, v):
        """
        :param int u:
        :param int v:
        """
        # 深さを合わせる
        if self.depths[u] > self.depths[v]:
            u, v = v, u
        for k in range(self.MAX_LOG_V):
            if (self.depths[v] - self.depths[u]) >> k & 1:
                v = self.parents[k][v]
        if v == u:
            return v

        # にぶたん
        for k in reversed(range(self.MAX_LOG_V)):
            if self.parents[k][u] != self.parents[k][v]:
                u = self.parents[k][u]
                v = self.parents[k][v]
        return self.parents[0][u]

    def distance(self, u, v):
        """
        u, v 間の距離
        depth[u] + depth[v] - depth[lca] * 2
        :param u:
        :param v:
        :rtype: int
        """
        lca = self.lca(u, v)
        return self.depths[u] + self.depths[v] - self.depths[lca] * 2


# 包除原理つかう

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
M = int(sys.stdin.buffer.readline())
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

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

root = 0
parents = [None] * N
stack = [(root, None)]
while stack:
    v, p = stack.pop()
    parents[v] = p
    for u in graph[v]:
        if u == p:
            continue
        stack.append((u, v))

lca = DoublingLCA(graph=graph, max_v=N - 1, root=root)
constraints = [0] * M
# 制約ごとにどの辺を使うかを持つ
for i, (v, u) in enumerate(VU):
    v -= 1
    u -= 1
    ancestor = lca.lca(v, u)
    while v != ancestor:
        constraints[i] |= 1 << edges_i[v, parents[v]]
        v = parents[v]
    while u != ancestor:
        constraints[i] |= 1 << edges_i[u, parents[u]]
        u = parents[u]


# for c in constraints:
#     print(np.binary_repr(c, 10))


def count(edges_bin):
    cnt = 0
    while edges_bin > 0:
        cnt += edges_bin & 1
        edges_bin >>= 1
    return pow(2, N - 1 - cnt)


# 余事象を数える
# 制約をいくつか選んだときに、1つ以上の制約を満たさない場合の数
# 1つの制約を満たさない数は、2^(制約と関係ない辺の数) == 2^((N - 1) - 使う辺の数)
ans = 0
for choice in range(1, 1 << M):
    cnt = 0
    edges = 0
    for i in range(choice.bit_length()):
        if choice >> i & 1:
            cnt += 1
            edges |= constraints[i]
    ans += count(edges) * (-1) ** (cnt - 1)
print(2 ** (N - 1) - ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter

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

M = int(input())
uv = [[int(i) for i in input().split()] for _ in range(M)]

cnt = [set() for _ in range(M)]
def dfs(cur, pre, dest, i) :
  if cur == dest :
    return True
  
  for nex, j in ab[cur] :
    if nex == pre :
      continue
    if dfs(nex, cur, dest, i) :
      cnt[i].add(j)
      return True

  return False

for i, (u, v) in enumerate(uv) :
  dfs(u - 1, -1, v - 1, i)

ret = 1 << (N - 1)
for i in range(1, 1 << M) :
  sgn = 1
  s = set([])
  for j in range(M) :
    if i & (1 << j) :
      s |= cnt[j]
      sgn *= -1
  ret += sgn * (1 << (N - 1 - len(s)))

print(ret)

Submission status: Accepted

Solution code:
n = int(input())

g = [[] for _ in range(n)]
edge = {}


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

m = int(input())


def dfs(u,v):
    visited = [False]*n
    visited[u] = True
    stack = [u]
    prev = [-1]*n
    while stack:
        uu = stack.pop()
        for vv in g[uu]:
            if not visited[vv]:
                visited[vv] = True
                prev[vv] = uu
                stack.append(vv)
        if prev[v] != -1:
            break
    bin_edge = 0
    head = v
    while head != u:
        bin_edge += 1 << edge[(head, prev[head])]
        head = prev[head]
    return bin_edge

intv = [0]*m

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


mm = 1 <<m

ans = 0

for i in range(mm):
    a = 0
    cnt = 0
    for j in range(m):
        if (i >> j) & 1:
            cnt += 1
            a = a | intv[j]
    white = str(bin(a)).count('1')
    ans += ((-1)**(cnt))*2**(n-1-white)

print(abs(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

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

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  condition=0
  for j in range(m):
    if i&(1<<j):#j番目の条件を満たす
      condition=condition|passing[j]
  cond_ct=popcount(condition) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append((b-1,i))
  Edge[b-1].append((a-1,i))
m=int(input())
M=[]
for i in range(m):
  M.append(tuple(map(int,input().split())))

inf=float("inf")
path=[-1]*n #根から各点までのパスが通過する辺をbitで管理したもの
path[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next,num in Edge[cur]:
    if path[next]==-1:
      path[next]=path[cur]|(1<<num)
      stack.append(next)

def popcount(x):
  return bin(x).count("1")

passing=[] #Mの各u,vについて、通過する辺をbitで持ったもの
for u,v in M:
  passing.append((path[u-1]^path[v-1]))

ans=2**(n-1)
#Mのすべての部分集合について符号付で足し合わせる
for i in range(1,2**m):
  i_ct=popcount(i)#満たすべき条件の数、これで符号を決める
  condition=0
  for j in range(m):
    if i&(1<<j):#j番目の条件を満たす
      condition=condition|passing[j]
  cond_ct=popcount(condition) #iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数

  ans+=pow((-1),i_ct)*pow(2,n-1-cond_ct)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def getPath(adj, start, goal):
    q = deque()
    q.appendleft((start, 0))
    while len(q):
        cur, p = q.pop()
        if cur == goal:
            return p
        for nxt, nhop in adj[cur]:
            if 2**nhop & p:
                continue
            npath = p | 2**nhop
            q.appendleft((nxt, npath))


def bitcount(x):
    return bin(x).count("1")


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add((b-1, i))
        adj[b-1].add((a-1, i))
    M = int(input())
    dp = [0] * (2**M)
    for i in range(M):
        u, v = map(int, input().split())
        path = getPath(adj, u-1, v-1)
        for j in range(2**i):
            dp[j + 2**i] = dp[j] | path
    ans = 0
    for i in range(2**M):
        ans += (-1) ** bitcount(i) * 2 ** (N - bitcount(dp[i]) - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def dfs(start, goal, tree):
    """startからgoalまでの木上のpathを出力する"""
    q = deque([start])
    visited = {}
    visited[start] = -1
    while True:
        pos = q.pop()
        if pos == goal:
            break
        for child in tree[pos]:
            if child in visited:
                continue
            visited[child] = pos
            q.append(child)
    res = []
    pos = goal
    while True:
        par = visited[pos]
        if par == -1:
            break
        res.append((min(par, pos), max(par, pos)))
        pos = par
    return res


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i
  

li_path = [0] * m
for i in range(m):
    s, g = path[i]
    s -= 1
    g -= 1
    res = dfs(s, g, tree)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i


def dfs(par, pos, goal):
    if pos == goal:
        return True
    for child in tree[pos]:
        if child == par:
            continue
        if dfs(pos, child, goal):
            res.append((min(pos, child), max(pos, child)))
            return True
    return False
  

li_path = [0] * m
for i in range(m):
    res = []
    s, g = path[i]
    s -= 1
    g -= 1
    dfs(-1, s, g)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)

Submission status: Accepted

Solution code:
# from itertools import combinations


# nは頂点数。lは[頂点,頂点]がn-1個入ったリスト。Tree(n, l)としてobjectを生成。
class Tree():
    def __init__(self, n, l):

        self.n = n

        # 隣接する頂点のリストが格納された辞書
        self.w = {}
        for i in range(n - 1):
            a, b, path = l[i]
            if a in self.w:
                self.w[a].append((b, path))
            else:
                self.w[a] = [(b, path)]
            if b in self.w:
                self.w[b].append((a, path))
            else:
                self.w[b] = [(a, path)]


    # rootを根とした時の、各頂点の一つ上の親の頂点が格納された辞書を返す。
    def make_parents_list(self, root):
        self.parents = {}
        que = []
        seen = {}
        for i in range(1, n + 1):
            seen[i] = 0
        self.parents[root] = (None, None)
        seen[root] = 1
        que.append(root)
        while len(que) != 0:
            node = que.pop()
            for k in range(len(self.w[node])):
                node_2, path_2 = self.w[node][k]
                if seen[node_2] == 0:
                    seen[node_2] = 1
                    que.append(node_2)
                    self.parents[node_2] = (node, path_2)
                else:
                    continue
        return self.parents


    # 頂点uと頂点vの最小共通祖先(LCA)を求める。
    def lca(self, root, u, v):
        ancestors = set()
        if self.parents is None:
            parents = self.make_parents_list(root)
        else:
            parents = self.parents
        parent = u

        while parent is not None:
            ancestors.add(parent)
            parent = parents[parent][0]

        node = v
        while node not in ancestors:
            node = parents[node][0]

        return node


n = int(input())
l = []
for i in range(n - 1):
    a, b = [int(_) for _ in input().split()]
    l.append((a, b, i))
tree = Tree(n, l)
seiyaku = []
parents = tree.make_parents_list(1)
m = int(input())
for i in range(m):
    u, v = [int(_) for _ in input().split()]
    parent_node = tree.lca(1, u, v)
    s = set()
    node = u
    while node != parent_node:
        s.add(parents[node][1])
        node = parents[node][0]
    node = v
    while node != parent_node:
        s.add(parents[node][1])
        node = parents[node][0]
    seiyaku.append(s)

ans = 2 ** (n - 1)
for i in range(1, 2 ** m):
    i_bin = format(i, '0' + str(m) + 'b')
    k = 0
    q = []
    for j in range(m):
        if i_bin[j] == '1':
            q.append(j)
            k += 1
        else:
            continue
    s = set()
    for x in q:
        s |= seiyaku[x]
    ans += (-1) ** k * 2 ** (n - 1 -len(s))
    # print('*****************')
    # print('i_bin = ' ,i_bin)
    # print('k = ', k)
    # print('q = ', q)
    # print('s = ', s)
    # print('len(s) = ', len(s))
    # print('(-1) ** k * 2 ** (n - 1 - len(s)) = ', (-1) ** k * 2 ** (n - 1 - len(s)))
    # print('ans = ', ans)
print(ans)

# print('+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++')

# cnt = 2**(n-1)

# f = 0
# for i in range(1, m+1):
#     flag = 1
#     if i % 2 == 1:
#         flag = -1
#     cc = combinations(list(range(m)), i)
#     for c in cc:
#         s = set()
#         for j in c:
#             s |= seiyaku[j]
#         cnt += (2**(n-1-len(s)))*flag
#         f += 1
#         print('*****************')
#         print('c = ' ,c)
#         print('flag = ', flag)
#         print('s = ', s)
#         print('len(s) = ', len(s))
#         print('(2**(n-1-len(s)))*flag = ', (2**(n-1-len(s)))*flag)
#         print('cnt = ', cnt)
# print(cnt)
# print('f = ', f)

Submission status: Accepted

Solution code:
n = int(input())
adj = [[] for _ in range(n)]
adj_dict = dict()

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
# edge-bitset of each set of constraints
edgest = [0] * 2**m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            edgest[1 << i] |= (1 << edge_dict[(uu, vv)])
for i in range(1, 2**m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]
 
# dp[set of constraints]
dp = [0] * 2**m
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    limit_num = bin(edgest[i] ^ edgest[i ^ lsb]).count("1")
    dp[i] = dp[i ^ lsb] >> limit_num
    # Inclusion and exclusion
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
# edge-bitset of each constraint
target_edge = [0] * m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            target_edge[i] |= (1 << edge_dict[(uu, vv)])

# edge-bitset of each set of constraints
edgest = [0] * 2**m
for i in range(1, 2**m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | target_edge[lsb.bit_length() - 1]
 
# dp[set of constraints]
dp = [0] * 2**m
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    n_edgest = edgest[i]
    p_edgest = edgest[i ^ lsb]
    limit_num = bin(n_edgest ^ p_edgest).count("1")
    dp[i] = dp[i ^ lsb] >> limit_num
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
target_edge = [0] * m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            target_edge[i] |= (1 << edge_dict[(uu, vv)])

edge_of_state = [0] * 2**m
for i in range(1, 2**m):
    lsb = i & (-i)
    edge_of_state[i] = edge_of_state[i ^ lsb] | target_edge[lsb.bit_length() - 1]
 
# dp[fills uv as st]
dp = [0] * 2**m
dp[0] = pow(2, n-1) 
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    n_edgest = edge_of_state[i]
    p_edgest = edge_of_state[i ^ lsb]
    limit_num = bin(n_edgest ^ p_edgest).count("1")
    dp[i] = dp[i ^ lsb] // pow(2, limit_num)
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)