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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
edges = []

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
        edges.append((b, a))
    else:
        edge_dict[(a, b)] = i
        edges.append((a, b))

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]

state = [set() for _ in range(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:
            state[i].add(edge_dict[(uu, vv)])

# DP[i-th item][fills uv as st]
dp = [[0] * 2**m for _ in range(n - 1)]
dp[0][0] = 1
a, b = edges[0]
status = 0
for i, st in enumerate(state):
    if 0 in st:
        status |= 1 << i
dp[0][status] = 1

for i, (a, b) in enumerate(edges):
    if i == 0:
        continue
    status = 0
    for j, st in enumerate(state):
        if i in st:
            status |= 1 << j
    for k in range(2**m):
        # Fill black
        dp[i][k | status] += dp[i-1][k]
        # Fill white
        dp[i][k] += dp[i-1][k]

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[set() for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i].add((s,t))
        x=parents[x]
#print(root)
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
L=sorted(list(range(2**M)),key=lambda x:cnt(x))
S=[set() for i in range(2**M)]
for i in L:
    if i==0:
        continue
    if cnt(i)==1:
        #print(i,len(bin(i))-3)
        S[i]={j for j in root[len(bin(i))-3]}
        ans+=2**(N-len(S[i])-1)
        continue
    x=-1
    for j in range(M):
        if i|(2**j)==i:
            x=2**j
            break
    y=i^x
    S[i]=S[x]|S[y]
    ans+=(-1)**(cnt(i)+1)*2**(N-len(S[i])-1)
print(2**(N-1)-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]


def bfs(s,n,g,t): # 木構造の距離の算出 start, number, graph
    went = [False]*n
    dis = [0]*n
    que = deque([])
    que.append(s)
    went[s] = True
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            que.append(g[go][i])
    root = []
    root.append(t)
    x = dis[t]
    que1 = deque([])
    que1.append(t)
    while que1:
        go = que1.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] == x-1:
                que1.append(g[go][i])
                root.append(g[go][i])
                x -=1
                break
        if x == 0:
            break
    return root


def main():
    n = inp()
    g=[[] for _ in range(n)]
    ab = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        ab.append((a,b))
        g[b].append(a)
        g[a].append(b)
    m = inp()
    ans = 0
    pre_root = []
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        root1 = bfs(u,n,g,v)
        pre_root.append(tuple(root1))
    for k in range(pow(2,n-1)):
        color = defaultdict(int)
        index = 0
        while index < n-1:
            [a,b] = ab[index]
            color[str(a)+' '+str(b)] = k%2
            color[str(b)+' '+str(a)] = k%2
            k //=2
            index += 1
        flag = 1
        for i in range(m):
            root = pre_root[i]
            flag1 = 1
            for j in range(len(root)-1):
                a,b = root[j],root[j+1]
                if color[str(a)+' '+str(b)] == 0:
                    flag1 = 0
                    break
            if flag1:
                flag = 0
                break
        if flag:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def dis(x1,y1,x2,y2): # 距離関数
    distance = ((x1-x2)**2 + (y1-y2)**2)**(1/2)
    return distance

def bfs(s,n,g,t): # 木構造の距離の算出 start, number, graph
    went = [False]*n
    dis = [0]*n
    que = deque([])
    que.append(s)
    went[s] = True
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            que.append(g[go][i])
    root = []
    root.append(t)
    x = dis[t]
    que1 = deque([])
    que1.append(t)
    while que1:
        go = que1.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] == x-1:
                que1.append(g[go][i])
                root.append(g[go][i])
                x -=1
                break
        if x == 0:
            break
    return root


def main():
    n = inp()
    g=[[] for _ in range(n)]
    ab = []
    for _ in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        ab.append((a,b))
        g[b].append(a)
        g[a].append(b)
    m = inp()
    ans = 0
    uv = []
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        uv.append((u,v))
    for k in range(pow(2,n-1)):
        color = defaultdict(int)
        index = 0
        while index < n-1:
            [a,b] = ab[index]
            color[str(a)+' '+str(b)] = k%2
            color[str(b)+' '+str(a)] = k%2
            k //=2
            index += 1
        flag = 1
        for i in range(m):
            root = bfs(uv[i][0],n,g,uv[i][1])
            flag1 = 1
            for j in range(len(root)-1):
                a,b = root[j],root[j+1]
                if color[str(a)+' '+str(b)] == 0:
                    flag1 = 0
                    break
            if flag1:
                flag = 0
                break
        if flag:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = [[] for _ in range(N)]
for i in range(N-1):
    a,b = inpl()
    a-=1; b-=1
    lines[a].append((b,i))
    lines[b].append((a,i))


def dfs(s,b,v):
    if s == v:
        return set()
    else:
        for t,i in lines[s]:
            if t == b:
                continue
            ret = dfs(t,s,v)
            if ret is not None:
                ret.add(i)
                return ret

        return None


M = inp()
mm = [] # i 番目の条件は mm[i] のラインのどこかに +1 をする
for m in range(M):
    u,v = inpl()
    u-=1; v-=1
    mm.append(dfs(u,-1,v))



dp = [0] * (1<<M)
dp[0] = 1

for i in range(N-1):
    # line i を白くした場合
    # dp[:] = dp[:]
    # line i を黒くした場合
    tmp = 0
    for b,m in enumerate(mm):
        if i in m:
            tmp += (1<<b)

    for b in reversed(range(1<<M)):
        dp[b | tmp] += dp[b]



print(dp[-1])

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    from itertools import combinations

    N = int(readline())

    edge = defaultdict(list)

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

    def bfs(s, g):
        que = deque()
        que.append((s, []))
        visited = [False] * N
        visited[s] = True

        while que:
            cur, path = que.popleft()
            if cur == g:
                return set(path)
            for nx, i in edge[cur]:
                if not visited[nx]:
                    new_path = path + [i]
                    que.append((nx, new_path))
                    visited[nx] = True

    M = int(readline())
    constraints = []
    for _ in range(M):
        u, v = map(int, readline().split())
        u -= 1
        v -= 1
        constraints.append(bfs(u, v))

    cnt = 0
    for i in range(1, M + 1):
        sign = 1 if i % 2 == 1 else -1
        for per in combinations(range(M), r=i):
            incl = set()
            for x in per:
                incl = incl.union(constraints[x])
            cnt += sign * 2 ** ((N - 1) - len(incl))

    print(2 ** (N - 1) - cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

M = int(input())
uvs = [tuple(map(int, input().split())) for _ in range(M)]

edges = [0] * (N - 1)
for i, (u, v) in enumerate(uvs):
    u -= 1
    v -= 1
    parent = [-1] * N
    stack = [u]
    while stack:
        node = stack.pop()
        if node == v:
            break

        for next_node in adj[node]:
            if parent[node] != next_node:
                parent[next_node] = node
                stack.append(next_node)
             
    node = v
    while node != u:
        next_node = parent[node]
        index = e_index[(node, next_node)]
        edges[index] |= 1 << i
        node = next_node

dp = [0] * (1 << M)
dp[0] = 1
for e in edges:
    for i in range((1 << M) - 1, -1, -1):
        dp[i | e] += dp[i]

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  # n: 頂点数
  # ki: 木
  # Euler Tour の構築
  S=[] # Euler Tour
  F=[0]*n # F[v]:vにはじめて訪れるステップ
  depth=[0]*n # 0を根としたときの深さ
  def dfs(v,pare,d):
      F[v]=len(S)
      depth[v]=d
      S.append(v)
      for i,w in ki[v]:
          if w==pare:continue
          dfs(w,v,d+1)
          S.append(v)
  dfs(0,-1,0)
  # Sをセグメント木に乗せる
  # u,vのLCAを求める:S[F[u]:F[v]+1]のなかでdepthが最小の頂点を探せば良い
  # F[u]:uに初めてたどるつくステップ
  # S[F[u]:F[v]+1]:はじめてuにたどり着いてつぎにvにたどるつくまでに訪れる頂点
  # 存在しない範囲は深さが他よりも大きくなるようにする
  INF = (n, None)
  # LCAを計算するクエリの前計算
  M = 2*n
  M0 = 2**(M-1).bit_length() # M以上で最小の2のべき乗
  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]]
  

  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1
  #print(path)
  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u].union(path[v])
        tmp=tmp-path[dd]
        memo[c]=tmp
      must_w=must_w.union(tmp)
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  # n: 頂点数
  # ki: 木
  # Euler Tour の構築
  S=[] # Euler Tour
  F=[0]*n # F[v]:vにはじめて訪れるステップ
  depth=[0]*n # 0を根としたときの深さ
  def dfs(v,pare,d):
      F[v]=len(S)
      depth[v]=d
      S.append(v)
      for i,w in ki[v]:
          if w==pare:continue
          dfs(w,v,d+1)
          S.append(v)
  dfs(0,-1,0)
  # Sをセグメント木に乗せる
  # u,vのLCAを求める:S[F[u]:F[v]+1]のなかでdepthが最小の頂点を探せば良い
  # F[u]:uに初めてたどるつくステップ
  # S[F[u]:F[v]+1]:はじめてuにたどり着いてつぎにvにたどるつくまでに訪れる頂点
  # 存在しない範囲は深さが他よりも大きくなるようにする
  INF = (n, None)
  # LCAを計算するクエリの前計算
  M = 2*n
  M0 = 2**(M-1).bit_length() # M以上で最小の2のべき乗
  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]]
  

  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u]|path[v]
        tmp-=path[dd]
        memo[c]=tmp
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  # n: 頂点数
  # ki: 木
  # Euler Tour の構築
  S=[] # Euler Tour
  F=[0]*n # F[v]:vにはじめて訪れるステップ
  depth=[0]*n # 0を根としたときの深さ
  def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
      if w==pare:continue
      dfs(w,v,d+1)
      S.append(v)
  dfs(0,-1,0)
  # Sをセグメント木に乗せる
  # u,vのLCAを求める:S[F[u]:F[v]+1]のなかでdepthが最小の頂点を探せば良い
  # F[u]:uに初めてたどるつくステップ
  # S[F[u]:F[v]+1]:はじめてuにたどり着いてつぎにvにたどるつくまでに訪れる頂点
  # 存在しない範囲は深さが他よりも大きくなるようにする
  INF = (n, None)
  # LCAを計算するクエリの前計算
  M = 2*n
  M0 = 2**(M-1).bit_length() # M以上で最小の2のべき乗
  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]]
  
  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      if c in memo:
        tmp=memo[c]
      else:
        u,v=uv[c]
        dd=query(u,v)
        tmp=path[u]|path[v]
        tmp-=path[dd]
        memo[c]=tmp
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main(n,ki,uv):
  # n: 頂点数
  # ki: 木
  # Euler Tour の構築
  S=[] # Euler Tour
  F=[0]*n # F[v]:vにはじめて訪れるステップ
  depth=[0]*n # 0を根としたときの深さ
  def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
      if w==pare:continue
      dfs(w,v,d+1)
      S.append(v)
  dfs(0,-1,0)
  # Sをセグメント木に乗せる
  # u,vのLCAを求める:S[F[u]:F[v]+1]のなかでdepthが最小の頂点を探せば良い
  # F[u]:uに初めてたどるつくステップ
  # S[F[u]:F[v]+1]:はじめてuにたどり着いてつぎにvにたどるつくまでに訪れる頂点
  # 存在しない範囲は深さが他よりも大きくなるようにする
  INF = (n, None)
  # LCAを計算するクエリの前計算
  M = 2*n
  M0 = 2**(M-1).bit_length() # M以上で最小の2のべき乗
  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]]
  
  todo=[[0,[]]]
  path=[[]]*n
  mi=[1]*n
  while todo:
    v,ary=todo.pop()
    path[v]=ary
    mi[v]=0
    for i,nv in ki[v]:
      if mi[nv]==1:
        todo.append([nv,ary+[i]])
        mi[nv]=1

  for i in range(n):
    path[i]=set(path[i])
  memo={}
  for c in range(m):
    u,v=uv[c]
    dd=query(u,v)
    tmp=path[u]|path[v]
    tmp-=path[dd]
    memo[c]=tmp

  ans=0
  for i in range(2**m):
    chk=set(())
    for j in range(m):
      if (i>>j)&1:
        chk.add(j)
    must_w=set(())
    for c in chk:
      tmp=memo[c]
      must_w|=tmp
    t=n-1-len(must_w)
    if len(chk)%2==1:
      ans-=pow(2,t)
    else:
      ans+=pow(2,t)
  print(ans)
if __name__=='__main__':
  n=int(input())
  ki=[[] for _ in range(n)]
  for i in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append([i,v])
    ki[v].append([i,u])
  m=int(input())
  uv=[]
  for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    uv.append([u,v])
  main(n,ki,uv)

Submission status: Accepted

Solution code:
from copy import copy
def dfs(x,v,s):
    for y,i in tree[x]:
        if parent[x] != y:
            parent[y] = x
            s.add(i)
            dfs(y,v,s)
            s.remove(i)
    if x == v:
        cons.append(s.copy())
    

N = int(input())
tree = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append((b,i))
    tree[b].append((a,i))
M = int(input())
uv = []
cons = []
for i in range(M):
    u,v =  map(int,input().split())
    uv.append((u,v))
    parent = [-1]*(N+1)
    dfs(u,v,set())
bit = [0]*(N-1)
for i in range(N):
    for j in range(M):
        if i in cons[j]:
            bit[i] += 1 << j
dp = [0]*(1 << M)
dp[0] = 1
for i in range(N-1):
    for j in range(1 << M)[::-1]:
        dp[j|bit[i]] += dp[j]
print(dp[-1])

Submission status: Accepted

Solution code:
from itertools import product

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


class Node:
    def __init__(self, nodeid, parent=None):
        self.nodeid = nodeid
        self.parent = parent
        self.children = []

    def add_child(self, nodeid, edgeid):
        child = Node(nodeid, parent=self)
        self.children.append((child, edgeid))

    def parents(self):
        if self.parent == None:
            return [self.nodeid]
        else:
            return [self.nodeid] + self.parent.parents()

    def path(self, to):
        if to == self.nodeid:
            return []
        for child, edgeid in self.children:
            try:
                ret = [edgeid] + child.path(to)
                return ret
            except ValueError:
                pass
        raise ValueError


root = Node(1)
nodes = {1: root}
leef = [root]
while len(leef) > 0:
    node = leef.pop()
    parentid = node.parent and node.parent.nodeid
    for i, (a, b) in enumerate(ab):
        if a == node.nodeid and b != parentid:
            node.add_child(b, i)
            leef.append(node.children[-1][0])
            nodes[b] = node.children[-1][0]
        elif b == node.nodeid and a != parentid:
            node.add_child(a, i)
            leef.append(node.children[-1][0])
            nodes[a] = node.children[-1][0]


constraints = [0]*M

for i, (u, v) in enumerate(uv):
    parents_u = nodes[u].parents()
    for p in nodes[v].parents():
        if p in parents_u:
            break
    for j in nodes[p].path(u):
        constraints[i] += pow(2, j)
    for j in nodes[p].path(v):
        constraints[i] += pow(2, j)

ans = 0
for idx in product([True, False], repeat=M):
    sumidx = sum(idx)
    constraint = 0
    for i, flg in enumerate(idx):
        if flg:
            constraint = constraint | constraints[i]
    C = bin(constraint)[2:].count('1')
    ans += pow(2, N-1-C) * ((-1)**(sumidx%2))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

    
def solve(N, M, Ok):
    def solve_half(Ok_half):
        # 半分の辺について全探索
        n = len(Ok_half)
        res = [0] * (1<<M)
        for set_black in range(1<<n):
            r = 0
            for i, Ok_i in enumerate(Ok_half):
                if set_black>>i&1:
                    r |= Ok_i
            res[r] += 1
        return res

    A = solve_half(Ok[:(N-1)//2])
    B = solve_half(Ok[(N-1)//2:])

    def fwt(A):
        n = len(A)
        #for i in range(n.bit_length()-1):
        for i in range(int(np.log2(n))):
            i = 1<<i
            for j in range(n):
                if i&j == 0:
                    A[j|i] += A[j]
        return A

    def ifwt(A):
        n = len(A)
        #for i in range(n.bit_length()-1):
        for i in range(int(np.log2(n))):
            i = 1<<i
            for j in range(n):
                if i&j == 0:
                    A[j|i] -= A[j]
        return A

    A = fwt(A)
    B = fwt(B)
    AB = [a*b for a, b in zip(A, B)]
    AB = ifwt(AB)
    return AB[-1]

numba_compile([
    [solve, "i8(i8,i8,i8[:])"],
])

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    Edges = []
    for _ in range(N - 1):
        a, b = sorted(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
        Edges.append((a, b))

    def dfs(v, target, p, Path):
        if v == target:
            Path.append(v)
            return True
        for u in G[v]:
            if p != u:
                f = dfs(u, target, v, Path)
                if f:
                    Path.append(v)
                    return True
        return False

    M = int(input())
    UV = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
    Ok = [0] * (N - 1)
    for idx_UV, (a, b) in enumerate(UV):
        Path = []
        dfs(a, b, -1, Path)
        for v, u in zip(Path, Path[1:]):
            v, u = sorted([v, u])
            idx_Edge = Edges.index((v, u))
            Ok[idx_Edge] |= 1 << idx_UV
    print(solve(N, M, np.array(Ok, dtype=np.int64)))

main()

Submission status: Accepted

Solution code:

import sys
def I():
    return int(sys.stdin.readline().rstrip())

def MI():
    return map(int, sys.stdin.readline().rstrip().split())


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

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

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

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

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

    # 包除原理

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    def I():
        return int(sys.stdin.readline().rstrip())

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

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

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

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

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

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

    # 包除原理

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

    print(ans)

if __name__ == '__main__':
    main()