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 itertools import combinations 
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
M = int(input())
uv = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
for a,b in ab:
    g[a].append(b)
    g[b].append(a)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    vtour = []
    etour = []
    depth = [-1]*(n+1)
    parent = [False]*(n+1)
    visited = [False]*(n+1)
    def dfs(v,d):
        depth[v] = d
        visited[v] = True
        ls[v] = len(vtour)
        vtour.append(v)
        etour.append(v)
        for nv in g[v]:
            if not visited[nv]:
                parent[nv] = v
                dfs(nv,d+1)
        rs[v] = len(vtour)
        etour.append(-v)
        vtour.append(parent[v])
    dfs(s,0)
    return ls,rs,etour,vtour,parent,depth

ls,rs,etour,vtour,parent,depth = eulerTour(g,1)
paths = []
depthind = [depth[v] for v in vtour]

for u,v in uv:
    l,r = ls[u],ls[v]
    l,r = (l,r) if l < r else (r,l)
    lcaind = depthind[l:r].index(min(depthind[l:r]))
    lca = vtour[l+lcaind]
    lpath = []
    x = u
    while x != lca:
        lpath.append(tuple(sorted((x,parent[x]))))
        x = parent[x]
    rpath = []
    x = v
    while x != lca:
        rpath.append(tuple(sorted((x,parent[x]))))
        x = parent[x]
    path = set(lpath + rpath)
    paths.append(path)
    
ans = 2**(N-1)

memo = {(i):paths[i] for i in range(M)}
memo[()] = set([])
for i in range(1,M+1):
    for vs in combinations(list(range(M)),i):
        sign = i % 2
        sect = memo[vs[:-1]] | paths[vs[-1]]
        memo[vs] = sect
        num = N-1 - len(sect)
        ans += (-1)**sign * (2**num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from functools import reduce
input = sys.stdin.readline
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
M = int(input())
uv = [list(map(int,input().split())) for i in range(M)]

g = defaultdict(list)
for a,b in ab:
    g[a].append(b)
    g[b].append(a)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    vtour = []
    etour = []
    depth = [-1]*(n+1)
    parent = [False]*(n+1)
    visited = [False]*(n+1)
    def dfs(v,d):
        depth[v] = d
        visited[v] = True
        ls[v] = len(vtour)
        vtour.append(v)
        etour.append(v)
        for nv in g[v]:
            if not visited[nv]:
                parent[nv] = v
                dfs(nv,d+1)
        rs[v] = len(vtour)
        etour.append(-v)
        vtour.append(parent[v])
    dfs(s,0)
    return ls,rs,etour,vtour,parent,depth

ls,rs,etour,vtour,parent,depth = eulerTour(g,1)
paths = []
depthind = [depth[v] for v in vtour]

for u,v in uv:
    l,r = ls[u],ls[v]
    l,r = (l,r) if l < r else (r,l)
    lcaind = depthind[l:r].index(min(depthind[l:r]))
    lca = vtour[l+lcaind]
    lpath = []
    x = u
    while x != lca:
        lpath.append(tuple(sorted((x,parent[x]))))
        x = parent[x]
    rpath = []
    x = v
    while x != lca:
        rpath.append(tuple(sorted((x,parent[x]))))
        x = parent[x]
    path = set(lpath + rpath)
    paths.append(path)
    
ans = 2**(N-1)

allv = set([v for v in range(1,N+1)])

for i in range(1,2**M):
    b = bin(i)[2:].zfill(M)
    b = list(map(lambda x: int(x),b))
    sign = sum(b) % 2
    pathset = [paths[i] for i in range(M) if b[i] == 1]
    sect = reduce(lambda x,y:x | y, pathset)
    num = N-1 - len(sect)
    ans += (-1)**sign * (2**num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC152F

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")




from collections import defaultdict
from queue import deque
import itertools
import functools
import numpy as np
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = np.zeros(n-1, dtype=bool)
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es[uv2e[u,seen[u]]] = True
        if seen[u]==start:
            break
        u = seen[u]
    return es

n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
    uv2e[u-1,v-1] = i
    uv2e[v-1, u-1] = i
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0

def dfs(ind, s, ans):
    if len(ind)==m:
        if True in ind:
            ans += 2**(n-1-s.sum()) * (-1)**((sum(ind)+1)%2)
        return ans
    ans = dfs(ind + [True], s | paths[len(ind)], ans)
    ans = dfs(ind + [False], s, ans)
    return ans
        
# for ind in itertools.product(*[(False, True) for _ in range(m)]):
#     num = sum(ind)+1
#     if num==1:
#         continue
#     c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
#     ans += (-1)**num * c
ans = dfs([], np.zeros(n-1, dtype=bool), 0)
print(2**(n-1) - ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC152F

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")





from collections import defaultdict
from queue import deque
import itertools
import functools
def find(start,goal):
    q = deque([start])
    seen = [None] * n
    seen[start] = -1
    while q:
        u = q.pop()
        d = seen[u]
        if u==goal:
            break
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    u = goal
    es = []
    while True:
        t = (min(u, seen[u]), max(u, seen[u]))
        es.append(t)
        if seen[u]==start:
            break
        u = seen[u]
    return set(es)

n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
    u, v = map(int, input().split())
    paths[i] = find(u-1,v-1)

ans = 0
for ind in itertools.product(*[(True, False) for _ in range(m)]):
    num = sum(ind)+1
    if num==1:
        continue
    c = 2**(n - 1 - len(functools.reduce(lambda x,y: x|y, (paths[i] for i in range(m) if ind[i]), set())))
    ans += (-1)**num * c
print(2**(n-1) - ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt, v, v_par, ans):
        ret = cnt[v]
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            ans += self.calc(cnt, v_next, v, 0)
            ret += cnt[v_next]
        cnt[v] = ret
        if ret == 0:
            ans += 1
        return ans


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

tree = Tree(n, graph, n // 2)

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

ans = 1 << (n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i, (u, v, lca) in enumerate(cond):
        if (bit >> i) & 1:
            cnt[u] += 1
            cnt[v] += 1
            cnt[lca] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt, 0, -1, 0) - 1
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**(l % 2)) * (1 << c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt, v, v_par, ans):
        ret = cnt[v]
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            ans += self.calc(cnt, v_next, v, 0)
            ret += cnt[v_next]
        cnt[v] = ret
        if ret == 0:
            ans += 1
        return ans


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

tree = Tree(n, graph, n // 2)

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

ans = 1 << (n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i, (u, v) in enumerate(cond):
        if (bit >> i) & 1:
            cnt[u] += 1
            cnt[v] += 1
            cnt[tree.lca_table[u][v]] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt, 0, -1, 0) - 1
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**(l % 2)) * (1 << c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt, v, v_par, ans):
        ret = cnt[v]
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            ans += self.calc(cnt, v_next, v, 0)
            ret += cnt[v_next]
        cnt[v] = ret
        if ret == 0:
            ans += 1
        return ans


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

tree = Tree(n, graph, n // 2)

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

ans = 1 << (n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i in range(m):
        if (bit >> i) & 1:
            cnt[cond[i][0]] += 1
            cnt[cond[i][1]] += 1
            cnt[tree.lca_table[cond[i][0]][cond[i][1]]] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt, 0, -1, 0) - 1
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**(l % 2)) * (1 << c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt):
        def _dfs(v, v_par, ans):
            ret = cnt[v]
            for v_next in self.graph[v]:
                if v_next == v_par:
                    continue
                ans += _dfs(v_next, v, 0)
                ret += cnt[v_next]
            cnt[v] = ret
            if ret == 0:
                ans += 1
            return ans

        return _dfs(0, -1, 0) - 1


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

tree = Tree(n, graph, n // 2)

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

ans = 1 << (n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i in range(m):
        if (bit >> i) & 1:
            cnt[cond[i][0]] += 1
            cnt[cond[i][1]] += 1
            cnt[tree.lca_table[cond[i][0]][cond[i][1]]] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt)
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**(l % 2)) * (1 << c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt):
        def _dfs(v, v_par, ans):
            ret = cnt[v]
            for v_next in self.graph[v]:
                if v_next == v_par:
                    continue
                ans += _dfs(v_next, v, 0)
                ret += cnt[v_next]
            cnt[v] = ret
            if ret == 0:
                ans += 1
            return ans

        return _dfs(0, -1, 0) - 1


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

tree = Tree(n, graph, n // 2)

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

ans = 2**(n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i in range(m):
        if (bit >> i) & 1:
            cnt[cond[i][0]] += 1
            cnt[cond[i][1]] += 1
            cnt[tree.lca_table[cond[i][0]][cond[i][1]]] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt)
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**l) * (2**c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt):
        def _dfs(v, v_par):
            ret = cnt[v]
            for v_next in self.graph[v]:
                if v_next == v_par:
                    continue
                _dfs(v_next, v)
                ret += cnt[v_next]
            cnt[v] = ret

        _dfs(0, -1)
        ans = 0
        for i in range(1, self.n):
            if cnt[i] == 0:
                ans += 1
        return ans


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

tree = Tree(n, graph, n // 2)

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

ans = 2**(n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i in range(m):
        if (bit >> i) & 1:
            cnt[cond[i][0]] += 1
            cnt[cond[i][1]] += 1
            cnt[tree.lca_table[cond[i][0]][cond[i][1]]] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt)
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**l) * (2**c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)


class Tree():
    def __init__(self, n, graph, v_root):
        self.n = n  # number of nodes
        self.graph = graph  # adjacent list of graph
        self.v_root = v_root  # root node

        self.logn = (self.n - 1).bit_length()
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.depth = [0] * self.n
        self.lca_table = [[-1] * self.n for _ in range(n)]

        self.init()

    def init(self):
        self.dfs(self.v_root, -1, 0)
        # doubling
        for k in range(self.logn - 1):
            for v in range(self.n):
                if self.parent[k][v] != -1:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]
        # create lca table
        for i in range(n):
            for j in range(n):
                self.lca_table[i][j] = self.lca(i, j)

    def dfs(self, v, v_par, depth):
        self.parent[0][v] = v_par
        self.depth[v] = depth
        for v_next in self.graph[v]:
            if v_next == v_par:
                continue
            self.dfs(v_next, v, depth + 1)

    def lca(self, u, v):
        if self.depth[u] > self.depth[v]:
            u, v = v, u

        # go to parents of v until same depth as u
        diff = self.depth[v] - self.depth[u]
        for k in range(diff.bit_length()):
            if diff & (1 << k):
                v = self.parent[k][v]
        if u == v:
            return u
        # binary search
        # for k in reversed(range(self.logn)):
        for k in range(self.depth[u].bit_length() - 1, -1, -1):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def calc(self, cnt):
        def _dfs(v, v_par):
            ret = cnt[v]
            for v_next in self.graph[v]:
                if v_next == v_par:
                    continue
                _dfs(v_next, v)
                ret += cnt[v_next]
            cnt[v] = ret

        _dfs(0, -1)
        ans = 0
        for i in range(1, self.n):
            if cnt[i] == 0:
                ans += 1
        return ans


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

tree = Tree(n, graph, 0)

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

ans = 2**(n - 1)
for bit in range(1, 1 << m):
    cnt = [0] * n
    l = 0
    for i in range(m):
        if (bit >> i) & 1:
            cnt[cond[i][0]] += 1
            cnt[cond[i][1]] += 1
            cnt[tree.lca_table[cond[i][0]][cond[i][1]]] -= 2
            l += 1

    # print(bin(bit), cnt)
    c = tree.calc(cnt)
    # print(bin(bit), cnt, c, l)
    ans += ((-1)**l) * (2**c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d


n = int(input())

wf = WarshallFloyd(n)
path = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
    wf.path(a-1,b-1,1)
d = wf.build()
m = int(input())
t = [set() for _ in range(m)]
for i in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    dist = d[u][v]
    for _ in range(dist):
        for p in path[v]:
            if d[u][p] + 1 == dist:
                dist -= 1
                t[i].add(min(p*100+v,p+v*100))
                v = p
X = [0]*m
combi = [0]*m
ans = 0
for i in range(1,m+1):
    for U in itertools.combinations(range(m),i):
        use = set()
        for u in U:
            use = use | t[u]
        combi[i-1] += 1
        X[i-1] += pow(2,n-1 - len(use))
    ans += X[i-1]*pow(-1,i-1)
print(pow(2,n-1) - ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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,i))
        g[b-1].append((a-1,i))

    def path(i,goal,mam=-1):
        if len(g[i][0])==1 and g[0]==mam:
            return 0
        else:
            for j,idx in g[i]:
                if j==mam:
                    continue
                if j==goal:
                    return 1<<idx
                p=path(j,goal,i)
                if p>0:
                    return p | (1<<idx)
            return 0

    m=int(input())
    ps=[]
    for _ in range(m):
        a,b=map(int,input().split())
        ps.append(path(a-1,b-1))

    import numpy as np
    dp=np.zeros(1<<m,dtype=np.int64)
    dp[0]=1
    for i in range(n-1):
        newdp=np.zeros(1<<m,dtype=np.int64)
        hit=0
        for j,p in enumerate(ps):
            a=p & (1<<i)
            if p & (1<<i):
                hit+=1<<j
        for j in range(1<<m):
            newdp[j|hit]+=dp[j]
        
        dp+=newdp
    print(dp[-1])
main()