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 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[f(parent, prev)].append(j)
            prev = parent
        prev = b
        for i in range(depth[b] - lca_depth):
            parent = par[prev]
            edge2cond[f(parent, 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[f(u, 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:


#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]
            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:
#包除原理
n = int(input())

TE = [[] for _ in range(n)]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai -= 1
    bi -= 1
    TE[ai].append(bi)
    TE[bi].append(ai)
m  = int(input())
D =[]
for i in range(m):
    ai,bi = map(int ,input().split( ))
    ai -= 1
    bi-=1
    D.append((ai,bi))

bit = 1<<m


P =[0]*n
C = [[] for _ in range(n)]
from collections import deque
Q = deque()
Q.append(0)
V = [0]*n 
V[0] = 1

while Q:
    v = Q.popleft()
    for u in TE[v]:
        if not V[u]:
            V[u] = 1
            Q.append(u)
            P[u] = v
            C[v].append(u)
def path(u,v):
    u_p = set()
    tmp1 = u
    while tmp1:
        u_p.add(tmp1)
        tmp1 = P[tmp1]
    u_p.add(tmp1)
    tmp2 = v

    while tmp2 not in u_p:
        tmp2 = P[tmp2]     
    pth = set()
    tmp3 = u
    tmp4 = v
    while tmp3!=tmp2:
        pth.add((tmp3,P[tmp3]))
        tmp3 = P[tmp3]
        
    while tmp4!= tmp2:
        pth.add((tmp4,P[tmp4]))
        tmp4 = P[tmp4]
    return pth
D2 = [path(D[i][0],D[i][1]) for i in range(m)]###
ans = 2**(n-1)
for i in range(1,bit):
    cnt = 0
    paths = set()
    for j in range(m):
        if (i>>j)&1:
            paths =paths | D2[j]
            cnt += 1
    ans += (-1)**cnt *2**(n-1-len(paths))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools
import sys

import numpy as np
import scipy.sparse

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

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

edges = np.zeros((n, n))
for a, b in ls0:
    edges[a, b] = 1
    edges[b, a] = 1
graph = scipy.sparse.csgraph.csgraph_from_dense(edges)
_, prevs_all = scipy.sparse.csgraph.dijkstra(graph, return_predecessors=True)

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

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

Submission status: Time Limit Exceeded

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

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        path.add((u, _u))
        u = _u
    while v!=w:
        _v = parent[v]
        path.add((v, _v))
        v = _v
    P.append(path)


ans = 0
n1 = N-1
for k in range(2**M):
    path = set()
    n = 0
    for i, p in enumerate(P):
        if (k>>i)&1:
            path |= p
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, n1-len(path))
    
print(pow(2, N-1) - ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools
import sys

import numpy as np
import scipy.sparse

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

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

edges = np.zeros((n, n))
for a, b in ls0:
    edges[a, b] = 1
    edges[b, a] = 1
graph = scipy.sparse.csgraph.csgraph_from_dense(edges)
_, prevs_all = scipy.sparse.csgraph.floyd_warshall(graph,
                                                   return_predecessors=True)

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

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

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

    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, prev)].append(j)
            prev = parent
        prev = b
        for i in range(depth[b] - lca_depth):
            parent = par[prev]
            edge2cond[(parent, 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, 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:
#包除原理
n = int(input())

TE = [[] for _ in range(n)]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai -= 1
    bi -= 1
    TE[ai].append(bi)
    TE[bi].append(ai)
m  = int(input())
D =[]
for i in range(m):
    ai,bi = map(int ,input().split( ))
    ai -= 1
    bi-=1
    D.append((ai,bi))

bit = 1<<m


P =[0]*n
C = [[] for _ in range(n)]
from collections import deque
Q = deque()
Q.append(0)
V = [0]*n 
V[0] = 1

while Q:
    v = Q.popleft()
    for u in TE[v]:
        if not V[u]:
            V[u] = 1
            Q.append(u)
            P[u] = v
            C[v].append(u)
def path(u,v):
    u_p = set()
    tmp1 = u
    while tmp1:
        u_p.add(tmp1)
        tmp1 = P[tmp1]
    u_p.add(tmp1)
    tmp2 = v

    while tmp2 not in u_p:
        tmp2 = P[tmp2]     
    pth = set()
    tmp3 = u
    tmp4 = v
    while tmp3!=tmp2:
        pth.add((tmp3,P[tmp3]))##点だとダメ
        tmp3 = P[tmp3]
        
    while tmp4!= tmp2:
        pth.add((tmp4,P[tmp4]))
        tmp4 = P[tmp4]
    return pth
ans = 2**(n-1)
for i in range(1,bit):
    cnt = 0
    paths = set()
    for j in range(m):
        if (i>>j)&1:
            paths =paths | path(D[j][0],D[j][1])
            cnt += 1
    ans += (-1)**cnt *2**(n-1-len(paths))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u, v, pu=-1):
        if u == v: return True
        for cu in to[u]:
            if cu == pu: continue
            if dfs(cu, v, u):
                path.append(uvtoi[u, cu])
                return True
        return False

    to = defaultdict(list)
    n = II()
    uvtoi = {}
    for i in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
        uvtoi[a, b] = i
        uvtoi[b, a] = i
    m = II()
    itoj = defaultdict(list)
    for j in range(m):
        u, v = MI1()
        path = []
        dfs(u, v)
        #print(path)
        for i in path: itoj[i].append(j)
    #print(itoj)
    en = len(itoj)
    dp = [[0] * (1 << m) for _ in range(en + 1)]
    dp[0][0] = 1
    for i, jj in enumerate(itoj.values()):
        mask = sum(1 << j for j in jj)
        for bit in range(1 << m):
            pre = dp[i][bit]
            if pre == 0: continue
            dp[i + 1][bit | mask] += pre
            dp[i + 1][bit] += pre
    #print(dp)
    ans=dp[-1][-1]*pow(2,n-1-en)
    print(ans)

main()

Submission status: Time Limit Exceeded

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

parent = [None]*N
depth = [0]*N
d = 0
queue = [0]
while queue:
    d += 1
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            parent[e] = q
            depth[e] = d
            queue_new.append(e)
    queue = queue_new

ancestor = [[None]*N for _ in range(N)]
for a in range(N):
    for b in range(a, N):
        _a = a
        _b = b
        while _a!=_b:
            if depth[_a] < depth[_b]: _b = parent[_b]
            else: _a = parent[_a]
        ancestor[a][b] = ancestor[b][a] = _a

M = int(input())
P = []
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    w = ancestor[u][v]
    path = set()
    while u!=w:
        _u = parent[u]
        path.add((u, _u))
        u = _u
    while v!=w:
        _v = parent[v]
        path.add((v, _v))
        v = _v
    P.append(path)


ans = 0
for k in range(2**M):
    path = set()
    n = 0
    for i in range(M):
        if (k>>i)&1:
            path |= P[i]
            n += 1

    if n==0: continue
    sign = +1 if n&1 else -1
    ans += sign * pow(2, N-1-len(path))
    
print(pow(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)]
    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
        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()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

v = []
path = []


def dfs(now, t, fa):
    if now == t:
        return 1
    for x, i in v[now]:
        if x == fa:
            continue
        if dfs(x, t, now):
            global path
            path.append(i)
            return 1
    return 0


b = []

n = int(input())
for i in range(n):
    v.append([])
for i in range(n-1):
    s = input().split(" ")
    x = int(s[0])-1
    y = int(s[1])-1
    v[x].append([y, i])
    v[y].append([x, i])
m = int(input())
for i in range(m):
    s = input().split(" ")
    x = int(s[0])-1
    y = int(s[1])-1
    path.clear()
    dfs(x, y, x)
    b.append(0)
    for z in path:
        b[i] |= (1 << z)
        # print('z='+str(z))


def count(x):
    cnt = 0
    while x > 0:
        if x % 2 == 1:
            cnt += 1
        x //= 2
    return cnt


ans = 1 << (n-1)
for S in range(1, 1 << m):
    bb = 0
    for i in range(m):
        if (S >> i) & 1:
            bb |= b[i]
    cnt = n-1-count(bb)
    # print('bb='+str(bb))
    # print('cnt='+str(cnt))
    if count(S) % 2 == 1:
        ans -= (1 << cnt)
    else:
        ans += (1 << cnt)

print(ans)

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
res = 2**(n - 1)
for k in range(1, m + 1):
    for comb in itertools.combinations(range(m), k):
        s = set()
        for j in comb:
            s |= paths[j]
        res += (-1)**len(comb) * 2**(n - 1 - len(s))
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product as p
n=int(input())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append([b,i])
    s[b].append([a,i])
m=int(input())
l=[]
for i in range(m):
    u,v=map(int,input().split())
    a=[[]for i in range(n+1)]
    a[u]=[]
    q=[u]
    while q:
        t=q.pop(0)
        d=0
        for i,j in s[t]:
            if a[i]==[]:
                a[i]=a[t]+[j]
                q.append(i)
                if i==v:
                    d=1
                    break
        if d==1:
            break
    l.append(a[v])
for i in range(m):l[i]=set(l[i])
s=[0]*(m+1)
for i in p([0,1],repeat=m):
    d=set([])
    if sum(i)!=0:
        for j in range(m):
            if i[j]:
                d|=l[j]
        s[sum(i)]+=pow(2,n-1-len(d))
l=0
for i in range(1,m+1):
    l+=((-1)**(i-1))*s[i]
print(pow(2,n-1)-l)

Submission status: Time Limit Exceeded

Solution code:
def dfs(s, t, links):
    visited = set()
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited.add(v)
        for l, u in links[v]:
            if u in visited:
                continue
            new_used = used | (1 << l)
            q.append((u, new_used))


n = int(input())
links = [set() for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add((i, b))
    links[b].add((i, a))
conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    conditions.append(dfs(u, v, links))

ans = 0
for i in range(1 << m):
    cnd_cnt = bin(i).count('1')
    bit = 0
    k = i
    while k:
        b = k & -k
        j = b.bit_length() - 1
        bit |= conditions[j]
        k ^= b
    free_link_cnt = n - 1 - bin(bit).count('1')
    val = 2 ** free_link_cnt
    if cnd_cnt % 2:
        ans -= val
    else:
        ans += val
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve(n, edge_list, m, cond_list):

    g = [[] for _ in range(n)]

    for a, b in edge_list:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    cond_mat = [[0] * m for _ in range(n - 1)]

    for i in range(m):
        u, v = cond_list[i]
        parent_list = [-1] * n
        p = u - 1
        parent_list[p] = p
        queue = deque([p])
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p]:
                if parent_list[q] == -1:
                    parent_list[q] = p
                    queue.append(q)
        q = v - 1
        p = parent_list[q]
        while q != u - 1:
            if (p + 1, q + 1) in edge_list:
                k = edge_list.index((p + 1, q + 1))
            else:
                k = edge_list.index((q + 1, p + 1))
            cond_mat[k][i] = 1
            p, q = parent_list[p], parent_list[q]

    # cond_vec
    cond_vec = [0] * (n - 1)
    for k in range(n - 1):
        for i in range(m):
            cond_vec[k] += cond_mat[k][i] * (2 ** i)
    # print(cond_vec)
    # bit DP
    dp = [[0] * (2 ** m) for _ in range(n)]
    dp[0][0] = 1
    for k in range(n - 1):
        for i in range(2 ** m):
            dp[k + 1][i] += dp[k][i]
            dp[k + 1][i | cond_vec[k]] += dp[k][i]
    # print(dp)
    return dp[-1][-1]


def main():
    n = int(input())
    edge_list = []
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge_list.append((a, b))
    m = int(input())
    cond_list = []
    for _ in range(m):
        u, v = map(int, input().split())
        cond_list.append((u, v))
    res = solve(n, edge_list, m, cond_list)
    print(res)


def test():
    assert solve(3, [(1, 2), (2, 3)], 1, [(1, 3)]) == 3
    assert solve(2, [(1, 2)], 1, [(1, 2)]) == 1
    assert solve(5, [(1, 2), (3, 2), (3, 4), (5, 3)], 3, [(1, 3), (2, 4), (2, 5)]) == 9


if __name__ == "__main__":
    test()
    main()