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:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll,E):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(E[(u,v)])
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    E = dict()
    for i in range(N-1):
        a, b = sorted(map(int, readline().split()))
        G[a].append(b)
        G[b].append(a)
        E[(a,b)] = i

    M, = map(int, readline().split())
    qes = dict()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        if u not in qes:
            qes[u] = list()
        qes[u].append(v)
    dep = []
    for i in qes:
        ms = qes[i]
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if u in ms:
                        dep.append(con(path+[u],E))
                    stack += [-v, u]
            else:
                path.pop()
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = set()
#        lns = 
        for j in range(M):
            if i % 2:
                ns = ns | dep[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-len(ns))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()

Submission status: Time Limit Exceeded

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

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

D = [[-1] * N for _ in range(N)]
for i in range(N - 1):
  a, b = ab[i][0] - 1, ab[i][1] - 1
  a, b = min(a, b), max(a, b)
  D[a][b] = i

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  L = T.dfs(x, y, r)
  n = L[0]
  t = 0
  for j in range(1, len(L)):
    m = L[j]
    x, y = min(n, m), max(n, m)
    t = t | (1 << D[x][y])
    n = m
  NL[i] = t
  

ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  D = [[0] * N for _ in range(N)]
  f = 0
  k = 0
  for j in range(M):
    if t & 1:
      f += 1
      k = k | NL[j]
    t >>= 1
  cnt = bin(k).count("1")
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))
print(ans - c)

Submission status: Time Limit Exceeded

Solution code:
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n = ii()
    e = [[]for i in range(n)]
    for i in range(n-1):
        a,b = mi()
        e[a-1].append([b-1,i])
        e[b-1].append([a-1,i])

    m = ii()
    mlist = []
    for i in range(m):
        u,v = mi()
        mlist.append([u-1,v-1])

    way = [[[]for i in range(n)] for j in range(n)]

    for s in range(n):
        stack = []
        waytmp = [0 for i in range(n-1)]
        stack.append([s,waytmp])
        while stack:
            tmp = stack.pop()
            p = tmp[0]
            for tt in tmp[1]:
                way[s][p].append(tt)
            for wtmp in e[p]:
                w = []
                for ttt in way[s][p]:
                    w.append(ttt)
                if w[wtmp[1]] == 1:
                    continue
                w[wtmp[1]] = 1
                stack.append([wtmp[0],w])

    ans = 0
    for _ in range(1,m+1):
        comall = itertools.combinations(range(m), _)
        for com in comall:
            wt = [0 for sdfhjk in range(n-1)]
            for w in com:
                for i in range(n-1):
                    wt[i] += way[mlist[w][0]][mlist[w][1]][i]
            cnt = 0
#            print("wt is ", wt)
            for i in range(n-1):
                if wt[i] == 0:
                    cnt+=1
            
#            print("cnt is ",cnt)
            if _%2:
                ans+=2**cnt
            else:
                ans-=2**cnt
    #print(way)
    print(2**(n-1)-ans)



    

        



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(100*u+v)
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    for v in range(N-1):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    M, = map(int, readline().split())
    qs = set()
    ss = set()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        qs.add((u,v))
        ss.add(u)
    dep = dict()
    for i in ss:
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if (i,u) in qs:
                        dep[(i,u)] = con(path+[u])
                    stack += [-v, u]
            else:
                path.pop()
    qs = list(qs)
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = set()
        for j in range(M):
            if i % 2:
                ns = ns | dep[qs[j]]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-len(ns))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()

Submission status: Time Limit Exceeded

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


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:
'''
包除原理
すべての条件を満たしている
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
q=deque([])
q.append(0)
S=[set() for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|{k for k in root[j]}
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-len(S[i])-1)
print(ans)

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:
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|{k for k in root[j]}
    ans+=(-1)**(cnt(i))*2**(N-len(S[i])-1)
print(ans)

Submission status: Time Limit Exceeded

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

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  NL[i] = T.dfs(x, y, r)
ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  D = [[0] * N for _ in range(N)]
  cnt = 0
  f = 0
  for j in range(M):
    if t & 1:
      f += 1
      L = NL[j]
      n = L[0]
      for k in range(1, len(L)):
        m = L[k]
        x, y = min(n, m), max(n, m)
        if D[x][y] == 0:
          cnt += 1
        D[x][y] += 1
        n = m
    t >>= 1
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))

print(ans - c)

Submission status: Time Limit Exceeded

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

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  D = [[0] * N for _ in range(N)]
  cnt = 0
  f = 0
  for j in range(M):
    if t & 1:
      f += 1
      x, y, r = uv[j][0] - 1, uv[j][1] - 1, uv[j][0] - 1
      L = T.dfs(x, y, r)
      n = L[0]
      for k in range(1, len(L)):
        m = L[k]
        x, y = min(n, m), max(n, m)
        if D[x][y] == 0:
          cnt += 1
        D[x][y] += 1
        n = m
    t >>= 1
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))

print(ans - c)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq
import itertools
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def compute(self, s, t):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        while q:
            dist_x, x = heapq.heappop(q)
            if x == t:
                return distances, prev_nodes

            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes

    def compute_all(self, s):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        for t in range(self.graph.n_nodes):
            heapq.heappush(q, (distances[t], t))
        while q:
            dist_x, x = heapq.heappop(q)
            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


n = ri()
ls0 = [(a - 1, b - 1) for a, b in rils(n - 1)]
m = ri()
ls1 = [(u - 1, v - 1) for u, v in rils(m)]

graph = Graph(n)
for a, b in ls0:
    graph.add_edge(a, b, 1, undirected=True)
dijkstra = Dijkstra(graph)

paths = collections.defaultdict(set)
for i, (u, v) in enumerate(ls1):
    _, prevs = dijkstra.compute(u, v)
    x = v
    while x != u:
        y = prevs[x]
        paths[i].add(tuple(sorted([x, y])))
        x = y

dic = collections.defaultdict(set)
res = 2**(n - 1)
for k in range(1, m + 1):
    for comb in itertools.combinations(range(m), k):
        dic[comb] = dic[tuple(comb[:-1])] | paths[comb[-1]]
        res += (-1)**len(comb) * 2**(n - 1 - len(dic[comb]))
print(res)

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
        path[str(a)+' '+str(b)] = i+1
        path[str(b)+' '+str(a)] = 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]
            x = path[str(a)+' '+str(b)]
            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:
def main():
    import sys
    from collections import defaultdict, deque
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 2 ** 31 - 1
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) // 2
                self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret = min(ret, self.seg_min[last])
                first = first // 2
                last = last // 2 - 1
            return ret

    def EulerTour(adj, root):
        st = [root]
        ret = []
        seen = [0] * len(adj)
        par = [0] * len(adj)
        depth = [0] * len(adj)
        while st:
            v = st.pop()
            if seen[v]:
                ret.append(v)
                continue
            ret.append(v)
            seen[v] = 1
            if par[v] != 0:
                st.append(par[v])
            for u in adj[v]:
                if seen[u] == 0:
                    st.append(u)
                    par[u] = v
                    depth[u] = depth[v] + 1

        return ret, depth, par

    def f(a, b):
        return a*100+b

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

    et, depth, par = EulerTour(adj, 1)
    segtree = SegTree(len(et) + 1)
    left = [-1] * (N + 1)
    right = [-1] * (N + 1)
    for i, v in enumerate(et):
        segtree.update(i + 1, depth[v])
        if left[v] < 0:
            left[v] = i
        right[v] = i

    M = int(input())
    edge2cond = defaultdict(list)
    for j in range(M):
        a, b = map(int, input().split())
        lca_depth = segtree.query(min(left[a], left[b]) + 1, max(right[a], right[b]) + 1)
        prev = a
        for i in range(depth[a] - lca_depth):
            parent = par[prev]
            edge2cond[parent*100+prev].append(j)
            prev = parent
        prev = b
        for i in range(depth[b] - lca_depth):
            parent = par[prev]
            edge2cond[parent*100+prev].append(j)
            prev = parent

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()
    dp = [[0] * (2**M) for _ in range(N)]
    dp[0][0] = 1
    for i, v in enumerate(seq):
        if v == 1:
            continue
        for mask in range(2**M):
            u = par[v]
            cond = edge2cond[u*100+v]
            mask_new = 0
            for k in cond:
                mask_new += 2**k
            dp[i+1][mask] += dp[i][mask]
            dp[i+1][mask | mask_new] += dp[i][mask]
    print(dp[-1][-1])
    #print(dp)
    #print(edge2cond)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N = int(input())

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

parent = [None]*N
visited = [False]*N
visited[0] = True
def rec(u):
    for v in adj[u]:
        if not visited[v]:
            parent[v] = u
            visited[v] = True
            rec(v)
rec(0)
del adj

M = int(input())


# edge_id to crucial query_id
tasks = [set() for _ in range(N)]

for q in range(M):
    u,v = map(int,input().split())
    u,v = u-1,v-1
    u2r = []
    v2r = []
    while u is not None:
        u2r.append(u)
        u = parent[u]
    while v is not None:
        v2r.append(v)
        v = parent[v]
    
    for i,(a,b) in enumerate(zip(reversed(u2r), reversed(v2r))):
        if a != b:
            break
    else:
        i += 1
    # path = u2r[:-i] + [u2r[-i]] + list(reversed(v2r[:-i]))

    for n in u2r[:-i]:
        tasks[n].add(q)
    for n in v2r[:-i]:
        tasks[n].add(q)

tasks = tasks[1:]

@lru_cache(None)
def rec(i, remainings):
    if i >= len(tasks):
        return 1 if not remainings else 0
    r = remainings & tasks[i]
    if not r:
        return 2*rec(i+1,remainings)

    #True
    return rec(i+1, remainings) + rec(i+1, frozenset(remainings-tasks[i]))

print(rec(0, frozenset(range(M))))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n = ii()
    e = [[]for i in range(n)]
    for i in range(n-1):
        a,b = mi()
        e[a-1].append([b-1,i])
        e[b-1].append([a-1,i])

    m = ii()
    mlist = []
    for i in range(m):
        u,v = mi()
        mlist.append([u-1,v-1])

    way = [[[]for i in range(n)] for j in range(n)]

    for s in range(n):
        stack = []
        waytmp = [0 for i in range(n-1)]
        stack.append([s,waytmp])
        while stack:
            tmp = stack.pop()
            p = tmp[0]
            way[s][p] = deepcopy(tmp[1])

            for wtmp in e[p]:
                w = deepcopy(way[s][p])
                if w[wtmp[1]] == 1:
                    continue
                w[wtmp[1]] = 1
                stack.append([wtmp[0],w])

    ans = 0
    for _ in range(1,m+1):
        comall = itertools.combinations(range(m), _)
        for com in comall:
            wt = [0 for sdfhjk in range(n-1)]
            for w in com:
                for i in range(n-1):
                    wt[i] += way[mlist[w][0]][mlist[w][1]][i]
            cnt = 0
#            print("wt is ", wt)
            for i in range(n-1):
                if wt[i] == 0:
                    cnt+=1
            
#            print("cnt is ",cnt)
            if _%2:
                ans+=2**cnt
            else:
                ans-=2**cnt
    #print(way)
    print(2**(n-1)-ans)



    

        



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 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
        path[str(a)+' '+str(b)] = i+1
        path[str(b)+' '+str(a)] = 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]
            x = path[str(a)+' '+str(b)]
            pre_root[j].append(x)
    for k in range(pow(2,n-1)):
        color = [0 for _ in range(n-1)]
        for i in range(n-1):
            color[i]=k%2
            k //= 2
            if k == 0:
                break
        flag = 1
        for i in range(m):
            flag1 = 0
            for j in range(len(pre_root[i])):
                go = pre_root[i][j]-1
                if color[go] == 1:
                    flag1 = 1
                    break
            if not flag1:
                flag = 0
                break
        if flag:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()