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:
def dfs(tree, v, tv, p, es):
    if v == tv:
        return True
    for e in tree[v]:
        if e[0] == p:
            continue
        if dfs(tree, e[0], tv, v, es):
            es.append(e[1])
            return True
    return False


def get_bit_count(bit):
    return format(bit, 'b').count('1')


def main():
    n = int(input())
    tree = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append((b, i))
        tree[b].append((a, i))
    m = int(input())
    eset = [0]*m
    for i in range(m):
        u, v = map(int, input().split())
        es = []
        dfs(tree, u-1, v-1, -1, es)
        for e in es:
            eset[i] |= 1 << e

    ans = 0
    for i in range(1 << m):
        mask = 0
        for j in range(m):
            if i >> j & 1:
                mask |= eset[j]
        white = get_bit_count(mask)
        now = 1 << (n-1-white)
        if get_bit_count(i) % 2 == 0:
            ans += now
        else:
            ans -= now
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def dfs(tree, v, tv, p, es):
    if v == tv:
        return True
    for e in tree[v]:
        if e[0] == p:
            continue
        if dfs(tree, e[0], tv, v, es):
            es.append(e[1])
            return True
    return False


def get_bit_count(bit):
    return format(bit, 'b').count('1')


def main():
    n = int(input())
    tree = {}
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a not in tree:
            tree[a] = []
        if b not in tree:
            tree[b] = []
        tree[a].append((b, i))
        tree[b].append((a, i))
    m = int(input())
    eset = [0]*m
    for i in range(m):
        u, v = map(int, input().split())
        es = []
        dfs(tree, u-1, v-1, -1, es)
        for e in es:
            eset[i] |= 1 << e

    ans = 0
    for i in range(1 << m):
        mask = 0
        for j in range(m):
            if i >> j & 1:
                mask |= eset[j]
        white = get_bit_count(mask)
        now = 1 << (n-1-white)
        if get_bit_count(i) % 2 == 0:
            ans += now
        else:
            ans -= now
    print(ans)


main()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]", M: int, u: "List[int]", v: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[a[i] - 1].append((b[i] - 1, i))
        conns[b[i] - 1].append((a[i] - 1, i))
    bits = []
    def dfs(idx, t, visited):
        visited[idx] = True
        if idx == t:
            return 0
        for node, edge_idx in conns[idx]:
            if not visited[node]:
                tmp = dfs(node, t, visited)
                if tmp is not None:
                    return tmp + (1 << edge_idx)
        return None
    for j in range(M):
        visited = [False] * N
        bit = dfs(u[j] - 1, v[j] - 1, visited)
        bits.append(bit)

    ret = 0
    for i in range(2 ** (N - 1)):
        for j in range(M):
            if i & bits[j] == 0:
                break
        else:
            ret += 1
    print(ret)
    return

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
M = int(input())
UV = [list(map(int,input().split())) for _ in [0]*M]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

P = [-1]*N
P[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if P[j]!=-1: continue
        P[j] = i
        q.append(j)
P[0] = -1

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

path = []
for u,v in UV:
    u -= 1
    v -= 1
    tmp = []
    d = dist_bfs(N,E,u)
    q = [v]
    while q:
        i = q.pop()
        di = d[i]
        for j in E[i]:
            if d[j] == di-1:
                q.append(j)
                if P[i]==j:
                    tmp.append(i)
                else:
                    tmp.append(j)
    path.append(set(tmp))

ans = 2**(N-1)
for i in range(1,2**M):
    tmp = set()
    cnt = 0
    for j in range(M):
        if (i>>j)&1==0:continue
        cnt += 1
        tmp = tmp | path[j]
    ans += ((-1)**cnt) * (2**(N-1-len(tmp)))
print(ans)

Submission status: Time Limit Exceeded

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

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 = [[set() for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, set()))
    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 | set([G[x][y]])
                q.append((y, s | set([G[x][y]])))
                reached[y] = True


ans = 2**(N-1)
a = set(range(N-1))
ans2 = 0
for i in range(1, M+1):
    for x in combinations(range(M), i):
        tmp = set(range(N-1))
        for y in x:
            u, v = uv[y]
            u -= 1
            v -= 1
            tmp &= (a - G2[u][v])
        #print(((-1)**(i-1)), len(tmp), tmp, x)
        ans2 += ((-1)**(i-1)) * 2 ** (len(tmp))
    #print(ans2, i)

print(ans-ans2)

Submission status: Time Limit Exceeded

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

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, M+1):
    for x in combinations(range(M), i):
        tmp = 2**(N-1) - 1
        for y in x:
            u, v = uv[y]
            u -= 1
            v -= 1
            tmp &= ~G2[u][v]
        ans2 += ((-1)**(i-1)) * 2 ** popcount(tmp)
    # print(ans2, i)

print(ans-ans2)

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)]
    path = defaultdict(int)
    for i in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        key = [str(a), ' ', str(b)]
        key = ''.join(key)        
        path[key] = i+1
        key = [str(b), ' ', str(a)]
        key = ''.join(key)     
        path[key] = i+1
        g[b].append(a)
        g[a].append(b)
    m = inp()
    ans = 0
    pre_root = [[] for _ in range(m)]
    for j in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        root1 = bfs(u,n,g,v)
        for i in range(len(root1)-1):
            a,b = root1[i],root1[i+1]
            key = [str(a), ' ', str(b)]
            key = ''.join(key)     
            x = path[key]
            pre_root[j].append(x)
    for k in range(pow(2,n-1)):
        flag = 1
        for i in range(m):
            flag1 = 0
            for j in range(len(pre_root[i])):
                go = pre_root[i][j]-1
                if (k>>go) & 1 == 1:
                    flag1 = 1
                    break
            if not flag1:
                flag = 0
                break           
        if flag:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

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

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+=((-1)**i_ct)*(2**(n-1-cond_ct))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def getPath(adj, start, goal):
    q = deque()
    q.appendleft((start, set()))
    while len(q):
        cur, p = q.pop()
        if cur == goal:
            return p
        for nxt, npath in adj[cur]:
            if npath in p:
                continue
            npath = p | {npath}
            q.appendleft((nxt, npath))


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 = [{tuple(): set()} for _ in range(M+1)]
    for i in range(M):
        u, v = map(int, input().split())
        dp[i+1] = dict(dp[i])
        path = getPath(adj, u-1, v-1)
        for t in dp[i]:
            dp[i+1][t + (i, )] = dp[i+1][t] | path
    ans = 0
    for key in dp[M]:
        ans += (-1) ** len(key) * 2 ** (N - len(dp[M][key]) - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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))
    path = [[None] * N for _ in range(N)]
    for i in range(N):
        start = i
        q = deque()
        q.appendleft((i, set()))
        while len(q):
            cur, p = q.pop()
            for nxt, npath in adj[cur]:
                if npath in p:
                    continue
                path[i][nxt] = p | {npath}
                q.appendleft((nxt, path[i][nxt]))
    M = int(input())
    dp = [{tuple(): set()} for _ in range(M+1)]
    for i in range(M):
        u, v = map(int, input().split())
        dp[i+1] = dict(dp[i])
        for t in dp[i]:
            dp[i+1][t + (i, )] = dp[i+1][t] | path[u-1][v-1]
    ans = 0
    for key in dp[M]:
        ans += (-1) ** len(key) * 2 ** (N - len(dp[M][key]) - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

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

def pop_count(b):
	return sum(map(int, list(bin(b)[2:])))

def dfs(x, p, bit):
	for v, j in adj[x]:
		if v == p or paths[p][v] > 0:
			continue
		paths[p][v] = bit + (1<<j)
		dfs(v, p, bit + (1<<j))
	return

for i in range(n):
	dfs(i, i, 0)

#print(*paths, sep="\n")

cons = []
m = int(input())
for _ in range(m):
	u, v = map(int, input().split())
	cons.append(paths[u-1][v-1])

#print(cons)

uses = [0 for _ in range(1<<m)]
ans = 1<<(n-1)
for b in range(1, 1<<m):
	pop = pop_count(b) % 2
	cur = 0
	while not (1<<cur) & b:
		cur += 1
	use = uses[b - (1<<cur)] | cons[cur]
	uses[b] = use
	if pop:
		ans -= 1 << (n-1 - pop_count(use))
	else:
		ans += 1 << (n-1 - pop_count(use))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append((b-1, i))
	adj[b-1].append((a-1, i))
paths = [[0 for _ in range(n)] for _ in range(n)]

def pop_count(b):
	return sum(map(int, list(bin(b)[2:])))

def dfs(x, p, bit):
	for v, j in adj[x]:
		if v == p or paths[p][v] > 0:
			continue
		paths[p][v] = bit + (1<<j)
		dfs(v, p, bit + (1<<j))
	return

for i in range(n):
	dfs(i, i, 0)

cons = []
m = int(input())
for _ in range(m):
	u, v = map(int, input().split())
	cons.append(paths[u-1][v-1])

ans = 1<<(n-1)
for b in range(1, 1<<m):
	use = 0
	pop = pop_count(b) % 2
	for i in range(m):
		if (b>>i) & 1 == 0:
			continue
		use |= cons[i]
	if pop:
		ans -= 1 << (n-1 - pop_count(use))
	else:
		ans += 1 << (n-1 - pop_count(use))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 方針
# 頂点uからvに至る際に通る辺のリストをe[u][v]とする。
# M個の制約からl個(l>=1)選んだ際に，いずれの制約も満たさないために白く塗るべき辺の個数を考える。
# これは,uiからviに至る際に通る辺のリストの和集合の要素の数。

from collections import deque

N = int(input())
adj = [[] for i in range(N + 1)] # 1-ind
ve = {} # 両端の頂点の番号⇒辺の番号
for i in range(1, N) : # 1-ind
    a, b = map(int,input().split())
    adj[a].append(b); adj[b].append(a)
    ve[(a, b)] = ve[(b, a)] = i
# print(adj) #DB
# print(ve) #DB

# 頂点iからスタートし，葉に行き着くまでの通過頂点とそれまでに通過した辺を記録
l = [[set() for j in range(N + 1)] for i in range(N + 1)]
q = deque()
for i in range(1, N + 1):
    r = [False] * (N + 1)
    q.append(i); r[i] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if r[v]:
                continue
            l[i][v].update(l[i][u])            
            l[i][v].add(ve[(u, v)])
            q.append(v)
            r[v] = True
# print(l) #DB
'''
for i in range(1, N + 1):
    for j in range(i, N + 1):
        print(i, j, l[i][j])
'''
M = int(input())
c = [set()]
for i in range(1, M + 1): # 1-ind
    u, v = map(int,input().split())
    c.append((u, v))

ans = 2 ** (N - 1)
for k in range(1, 1 << M): # 制約0個の場合を除外 ※初期値で考慮することもできそう
    V = set()
    d = 0 # 考慮する制約の個数
    for i in range(1, M + 1):
        if k >> (i - 1) & 1:
            d += 1
            u, v = c[i]
            V |= l[u][v]
    # print(k, V)
    temp = 2 ** (N - 1 - len(V))
    # print(d, temp)
    if d % 2 == 1:
        ans -= temp
    elif d % 2 == 0:
        ans += temp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from functools import reduce
from operator import or_, xor
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N-1)]
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(AB):
        G[a-1].append((b-1, i))
        G[b-1].append((a-1, i))
    M = int(input())

    def dfs(p):
        u = p[0] - 1
        v = p[1] - 1
        path = []
        visited = [False] * len(G)
        visited[u] = True
        def dfs_(x):
            if x == v: return True
            for y, i in G[x]:
                if not visited[y]:
                    visited[y] = True
                    if dfs_(y):
                        path.append(i)
                        return True
            return False
        dfs_(u)
        return reduce_or(map(pow2, path))

    def reduce_or(L): 
        def g():
            yield 0
            yield from L
        return reduce(or_, g())

    POW2 = [1 << x for x in range(51)]
    def pow2(x): return POW2[x]
    E = [dfs(tuple(map(int, input().split()))) for _ in range(M)]
    print(sum(POW2[N - 1 - bin(reduce_or(e for e, p in zip(E, prod) if p)).count("1")] * (-1 if reduce(xor, prod) else 1) for prod in product((True, False), repeat=M)))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from functools import reduce
from operator import or_, xor

def dfs(u, v, G):
    path = []
    visited = [False] * len(G)
    visited[u] = True
    def dfs_(x):
        if x == v: return True
        for y, i in G[x]:
            if not visited[y]:
                visited[y] = True
                if dfs_(y):
                    path.append(i)
                    return True
        return False
    dfs_(u)
    return path

def reduce_or(L): 
    def g():
        yield 0
        yield from L
    return reduce(or_, g())

def pow2(x): return 1 << x
def path2mask(P): return reduce_or(map(pow2, P))

def main():
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N-1)]
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(AB):
        G[a-1].append((b-1, i))
        G[b-1].append((a-1, i))
    M = int(input())
    UV = [tuple(map(int, input().split())) for _ in range(M)]
    E = [path2mask(dfs(u-1, v-1, G)) for u, v in UV]
    ans = 0
    for prod in product((True, False), repeat=M):
        mask = reduce_or(e for e, p in zip(E, prod) if p)
        a = 1 << N - 1 - bin(mask).count("1")
        ans += a * (-1) ** reduce(xor, prod)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
import sys


def memoize(fun):
    d = {}
    def wrap(*args):
        if args in d:
            return d[args]
        r = fun(*args)
        d[args] = r
        return r
    return wrap


def solve(N: int, a: "List[int]", b: "List[int]", M: int, u: "List[int]", v: "List[int]"):
    g = defaultdict(dict)
    for i, (ai, bi) in enumerate(zip(a, b)):
        g[ai][bi] = g[bi][ai] = i

    @memoize
    def get_path(p1, p2, fr):
        if p1 == p2:
            return []
        for mp, e in g[p1].items():
            if e == fr:
                continue
            pt = get_path(mp, p2, e)
            if pt is not None:
                return [e] + pt
        return None

    em = defaultdict(set)
    for i, (ui, vi) in enumerate(zip(u, v)):
        pt = get_path(ui, vi, None)
        for ei in pt:
            em[ei].add(i)

    dp = defaultdict(int)
    dp[(False,) * M] = 1
    for ei in range(N - 1):
        ptn_ = [False] * M
        for constr in em[ei]:
            ptn_[constr] = True
        ptn = tuple(ptn_)
        ndp = dp.copy()
        for ptn0, pv in dp.items():
            ndp[tuple(p0 or p for p0, p in zip(ptn0, ptn))] += pv
        dp = ndp
    print(dp[(True,) * M])


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


N = int(input())
g = Graph()
d = {}
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    d[(min(a,b),max(a,b))] = i
    g.add_edge(a,b)
    g.add_edge(b,a)

M = int(input())
l = [0]*M
for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    dij = Dijkstra(g,u)
    path = dij.shortest_path(v)
    for j in range(len(path)-1):
        a,b = path[j],path[j+1]
        l[i] += 2**d[(min(a,b),max(a,b))]

c = [0]*(M+1)
for n in range(2**M):
    cnt = 0
    x = 0
    for i in range(M):
        if n&2**i==2**i:
            cnt += 1
            x |= l[i]
    y = 0
    for i in range(N-1):
        if x&2**i==2**i:
            y += 1
    c[cnt] += 2**(N-1-y)

ans = 0
for i in range(M+1):
    if i%2==0:
        ans += c[i]
    else:
        ans -= c[i]

print(ans)