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
sys.setrecursionlimit(10**7)

n=int(input())
kk=[[] for _ in range(n)]
ki=[[] for _ in range(n)]
for i in range(n-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  kk[u].append([i,v])
  kk[v].append([i,u])
m=int(input())
uv=[]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  uv.append([u,v])

todo=[0]
ka=set(())
while todo:
  v=todo.pop()
  ka.add(v)
  for i,nv in kk[v]:
    if nv not in ka:
      ki[v].append([i,nv])
      todo.append(nv)


# n: 頂点数
# ki[v]: 頂点vの子頂点 (親頂点は含まない)
# Euler Tour の構築
S=[]
F=[0]*n
depth=[0]*n
def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
        if w==pare:continue
        dfs(w,v,d+1)
        S.append(v)
dfs(0,-1,0)
#print(S)
# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (n, None)

# LCAを計算するクエリの前計算
M = 2*n
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])

# LCAの計算 (generatorで最小値を求める)
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]
d={}

todo=[[0,[]]]
path=[[]]*n
mi=[1]*n
while todo:
  v,ary=todo.pop()
  path[v]=ary
  mi[v]=0
  for i,nv in ki[v]:
    if mi[nv]==1:
      todo.append([nv,ary+[i]])
      mi[nv]=1
#print(path)
for i in range(n):
  path[i]=set(path[i])
ans=2**(n-1)
for i in range(2**m):
  chk=[]
  for j in range(m):
    if (i>>j)&1:
      chk.append(j)
  if not chk:continue
  must_w=set(())
  for c in chk:
    u,v=uv[c]
    if (u,v) in d:
      dd=d[(u,v)]
    else:
      dd=query(u,v)
      d[(u,v)]=dd
    tmp=path[u].union(path[v])
    tmp=tmp-path[dd]
    must_w=must_w.union(tmp)
  t=n-1-len(must_w)
  if len(chk)%2==1:
    ans-=pow(2,t)
  else:
    ans+=pow(2,t)
print(ans)

Submission status: Time Limit Exceeded

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

n=int(input())
kk=[[] for _ in range(n)]
ki=[[] for _ in range(n)]
for i in range(n-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  kk[u].append([i,v])
  kk[v].append([i,u])
m=int(input())
uv=[]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  uv.append([u,v])

todo=[0]
ka=set(())
while todo:
  v=todo.pop()
  ka.add(v)
  for i,nv in kk[v]:
    if nv not in ka:
      ki[v].append([i,nv])
      todo.append(nv)


# n: 頂点数
# ki[v]: 頂点vの子頂点 (親頂点は含まない)
# Euler Tour の構築
S=[]
F=[0]*n
depth=[0]*n
def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
        if w==pare:continue
        dfs(w,v,d+1)
        S.append(v)
dfs(0,-1,0)
#print(S)
# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (n, None)

# LCAを計算するクエリの前計算
M = 2*n
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])

# LCAの計算 (generatorで最小値を求める)
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]


todo=[[0,[]]]
path=[[]]*n
mi=[1]*n
while todo:
  v,ary=todo.pop()
  path[v]=ary
  mi[v]=0
  for i,nv in ki[v]:
    if mi[nv]==1:
      todo.append([nv,ary+[i]])
      mi[nv]=1
#print(path)
for i in range(n):
  path[i]=set(path[i])
ans=2**(n-1)
for i in range(2**m):
  chk=[]
  for j in range(m):
    if (i>>j)&1:
      chk.append(j)
  if not chk:continue
  must_w=set(())
  for c in chk:
    u,v=uv[c]
    d=query(u,v)
    tmp=path[u].union(path[v])
    tmp=tmp-path[d]
    must_w=must_w.union(tmp)
  t=n-1-len(must_w)
  if len(chk)%2==1:
    ans-=pow(2,t)
  else:
    ans+=pow(2,t)
print(ans)

Submission status: Time Limit Exceeded

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

n=int(input())
kk=[[] for _ in range(n)]
ki=[[] for _ in range(n)]
for i in range(n-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  kk[u].append([i,v])
  kk[v].append([i,u])
m=int(input())
uv=[]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  uv.append([u,v])

todo=[0]
ka=set(())
while todo:
  v=todo.pop()
  ka.add(v)
  for i,nv in kk[v]:
    if nv not in ka:
      ki[v].append([i,nv])
      todo.append(nv)


# n: 頂点数
# ki[v]: 頂点vの子頂点 (親頂点は含まない)
# Euler Tour の構築
S=[]
F=[0]*n
depth=[0]*n
def dfs(v,pare,d):
    F[v]=len(S)
    depth[v]=d
    S.append(v)
    for i,w in ki[v]:
        if w==pare:continue
        dfs(w,v,d+1)
        S.append(v)
dfs(0,-1,0)
#print(S)
# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (n, None)

# LCAを計算するクエリの前計算
M = 2*n
M0 = 2**(M-1).bit_length()
data = [INF]*(2*M0)
for i, v in enumerate(S):
    data[M0-1+i] = (depth[v], i)
for i in range(M0-2, -1, -1):
    data[i] = min(data[2*i+1], data[2*i+2])

# LCAの計算 (generatorで最小値を求める)
def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1
# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]


todo=[[0,set(())]]
path=[set()]*n
mi=[1]*n
while todo:
  v,ary=todo.pop()
  path[v]=ary
  mi[v]=0
  for i,nv in ki[v]:
    if mi[nv]==1:
      ary.add(i)
      todo.append([nv,ary.copy()])
      ary.discard(i)
      mi[nv]=1
#print(path)
ans=2**(n-1)
for i in range(2**m):
  chk=[]
  for j in range(m):
    if (i>>j)&1:
      chk.append(j)
  if not chk:continue
  must_w=set(())
  for c in chk:
    u,v=uv[c]
    d=query(u,v)
    tmp=path[u].union(path[v])
    tmp=tmp-path[d]
    must_w=must_w.union(tmp)
  t=n-1-len(must_w)
  if len(chk)%2==1:
    ans-=pow(2,t)
  else:
    ans+=pow(2,t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product

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


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

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

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

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


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


constraints = np.array([[False] * (N - 1) for _ in range(M)])

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

ans = 0
for idx in product([True, False], repeat=M):
    sumidx = np.sum(idx)
    idx = [i for i, flg in enumerate(idx) if flg == True]
    if sumidx == 0:
        C = 0
    elif sumidx == 1:
        C = np.sum(constraints[idx][0])
    else:
        C = np.sum(np.sum(constraints[idx], axis=0) != 0)
    ans += pow(2, N-1-C) * ((-1)**(sumidx%2))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

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

        for next_node in adj[node]:
            if parent[node] != next_node:
                parent[next_node] = node
                stack.append(next_node)
                
    mask = 0
    node = v
    while node != u:
        next_node = parent[node]
        i = v_index[(node, next_node)]
        mask |= 1 << i
        node = next_node
    masks.append(mask)

# print(masks)

ans = 0
for bits in range(1 << (N-1)):
    for mask in masks:
        if not bits & mask:
            break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[] for _ in range(N)]
Edges = []
for _ in range(N-1):
    a, b = sorted(map(int, input().split()))
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    Edges.append((a, b))
def dfs(v, target, p, Path):
    if v == target:
        Path.append(v)
        return True
    for u in G[v]:
        if p != u:
            f = dfs(u, target, v, Path)
            if f:
                Path.append(v)
                return True
    return False
M = int(input())
UV = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]
Ok = [0] * (N-1)
for idx_UV, (a, b) in enumerate(UV):
    Path = []
    dfs(a, b, -1, Path)
    for v, u in zip(Path, Path[1:]):
        v, u = sorted([v, u])
        idx_Edge = Edges.index((v, u))
        Ok[idx_Edge] |= 1<<idx_UV

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

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

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

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

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

Submission status: Time Limit Exceeded

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

def dfs(G, p, pre, t, edge, x):
    for nxt in G[p]:
        if nxt == pre:
            continue
        a, b = p, nxt
        if b < a:
            a, b = b, a
        if nxt == t:
            edge[(a, b)] += x
            return True
        if dfs(G, nxt, p, t, edge, x):
            edge[(a, b)] += x
            return True
    return False

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    edge = {}
    for _ in range(n-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)
        if b < a:
            a, b = b, a
        edge[(a, b)] = 0
    m = int(input())
    for i in range(m):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        x = 1<<i
        dfs(G, u, -1, v, edge, x)
    ans = 2**(n-1)
    for i in range(1, 2**m):
        bit_cnt = 0
        for j in range(m):
            if (i & (1<<j)) != 0:
                bit_cnt += 1
        cnt = 0
        for v in edge.values():
            if (v & i) != 0:
                cnt += 1
        x = 2**(n-1 - cnt)
        if bit_cnt % 2 == 0:
            ans += x
        else:
            ans -= x
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def get_path(from_node, to_node, adj, nodes2edge):
    # from_nodeからto_nodeまでの最短パスで通るedgeを返す

    def dfs(node, parent, edges):
        if node == to_node:
            return edges
        min_path = None
        for child in adj[node]:
            if child == parent:
                continue
            path = dfs(child, node, edges + [nodes2edge[(node, child)]])
            if path is None:
                continue
            if min_path is None or len(min_path) > len(path):
                min_path = path
        return min_path

    return dfs(from_node, None, list())


def count_bits(n):
    return len([i for i in range(len('{:b}'.format(n))) if (n >> i) & 1 == 1])


def main():
    N = int(input())
    adj = defaultdict(list)
    nodes2edge = defaultdict(lambda :-1)
    for i in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
        nodes2edge[(a, b)] = i
        nodes2edge[(b, a)] = i
    M = int(input())
    constraints = [list(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(M)]
    # 各制約を「パス u->v 上の辺はすべて白」として扱い、包除原理で計算
    base = [0] * M  # 各制約で出てくる最短 u->v パス で通るedgeの2進表記
    for m, constraint in enumerate(constraints):
        u, v = constraint
        path = get_path(u, v, adj, nodes2edge)
        v = sum([2**e for e in path])
        base[m] = v
    dp = [0] * (2**M)  # 制約の集合で出てくる最短 u->v パスで通るedgeの和集合の2進表記
    ans = 2**(N - 1)
    for S in range(1, 2**M):
        lenbit_s = len('{:b}'.format(S))
        dp[S] = dp[S - (1 << (lenbit_s - 1))] | base[lenbit_s - 1]
        cnt_s = count_bits(S)
        cnt_dp = count_bits(dp[S])
        ans += (-1)**(cnt_s % 2) * 2**(N - 1 - cnt_dp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

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

M = int(input())
restriction = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

t = Tree(N, edge)
t.setroot(0)
t.heavylight_decomposition()

white_node = [[0 for j in range(N - 1)] for i in range(M)]

for i in range(M):
    u, v = restriction[i]
    for lt, rt in t.range_hld(u, v, 1):
        for j in range(lt, rt):
            white_node[i][j - 1] = 1

res = 0

for bit in range(2**M):
    cnt = 0
    det = [0 for _ in range(N - 1)]
    for i in range(M):
        if (bit >> i) & 1:
            cnt += 1
            for j in range(N - 1):
                if white_node[i][j]:
                    det[j] = 1
    if cnt % 2 == 0:
        res += 2**(N - 1 - sum(det))
    else:
        res -= 2**(N - 1 - sum(det))

print(res)

Submission status: Time Limit Exceeded

Solution code:
#F - Tree and constraints
import itertools
from collections import defaultdict
N = int(input())
G = [[] for i in range(N+1)]
edge = defaultdict(int)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[(min(a, b), max(a, b))] = i+1
    G[a].append(b)
    G[b].append(a)
M = int(input())
que = [tuple(map(int, input().split())) for i in range(M)]
Data = [set([]) for i in range(M)]


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)


for i in range(M):
    s, g = que[i]
    visited = [False for i in range(N+1)]
    parent = [-1 for i in range(N+1)]
    dfs(s)
    now = g
    while parent[now] > 0:
        number = edge[(min(now, parent[now]), max(now, parent[now]))]
        Data[i].add(number)
        now = parent[now]
ans = 2**(N-1)

for i in range(1, M+1):
    # Mこからi+1こを選ぶ
    S = 0
    subset = set([])
    for v in itertools.combinations(Data, i):
        subset.clear()
        for x in v:
            subset = x | subset
        S += 2**(N-1-len(subset))
    ans -= (-1)**((i-1) % 2)*S
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

def all_bit_count(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

n = int(readline())
g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)
  
m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,set()))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            que.append((i,L|{(mi,ma)}))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = set()
    for k in j:
      K |= k
    l = len(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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
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
    
m = int(input())
uvs = [None]*m
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    uvs[i] = (u,v)
    
from queue import deque    
def bfs(start):
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = u
                q.appendleft(v)
    return seen
ans = 0
def dfs(l, s):
    if len(l)==m:
        global ans
        val = pow(2, n-1-len(s)) * pow(-1, sum(l))
        ans += val
#         print(val, sum(l), ans)
        return
    dfs(l + [0], s)
    i = len(l)
    u,v = uvs[i]
    seen = bfs(u)
    ss = set()
    z = v
    while z!=u:
        z1 = seen[z]
        ss.add(uv2e[z,z1])
        z = z1
    dfs(l + [1], s|ss)
dfs([], set())
# ans = pow(2,n-1) - ans
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(n - 1))
m = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(m))
graph = [[] for _ in range(n + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
# LCAが必要そう
# 慣れないけどdoublingしてみる？
# 実行時間に余裕があるし、毎回DFSしていい気がしてきた。
# 通った辺を(a,b)の形でsetに打ち込んで全部白になる場合の数を調べる方針


def dfs(s, g):
    kouho = set()
    par = [-1] * (n + 1)
    depth = [0] * (n + 1)
    stack = []
    stack.append(s)
    while stack:
        v = stack.pop()
        if v == g:
            break
        d = depth[v]
        for u in graph[v]:
            if u == par[v]:
                continue
            par[u] = v
            depth[u] = d + 1
            stack.append(u)
    # 経路復元
    p = g
    q = par[g]
    while q > 0:
        kouho.add((min(p, q), max(p, q)))
        p = q
        q = par[q]
    return kouho


sets = [[] for _ in range(m)]
for i, (u, v) in enumerate(UV):
    sets[i] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
    kumiawase = list(combinations(range(m), i))
    for kumi in kumiawase:
        temp = set()
        for j in range(i):
            temp |= sets[kumi[j]]
        num = len(list(temp))
        ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import sys

input = sys.stdin.buffer.readline

n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
# LCAが必要そう
# 慣れないけどdoublingしてみる？
# 実行時間に余裕があるし、毎回DFSしていい気がしてきた。
# 通った辺を(a,b)の形でsetに打ち込んで全部白になる場合の数を調べる方針


def dfs(s, g):
    kouho = set()
    par = [-1] * (n + 1)
    depth = [0] * (n + 1)
    stack = []
    stack.append(s)
    while stack:
        v = stack.pop()
        if v == g:
            break
        d = depth[v]
        for u in graph[v]:
            if u == par[v]:
                continue
            par[u] = v
            depth[u] = d + 1
            stack.append(u)
    # 経路復元
    p = g
    q = par[g]
    while q > 0:
        kouho.add((min(p, q), max(p, q)))
        p = q
        q = par[q]
    return kouho


m = int(input())
sets = [[] for _ in range(m)]
for i in range(m):
    u, v = map(int, input().split())
    sets[i] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
    kumiawase = list(combinations(range(m), i))
    for kumi in kumiawase:
        temp = set()
        for j in range(i):
            temp |= sets[kumi[j]]
        num = len(list(temp))
        ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))

print(ans)

Submission status: Time Limit Exceeded

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

def solve():
    N = int(input())
    adjL = [[] for _ in range(N)]
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        adjL[a].append(b)
        adjL[b].append(a)
        edges.append((a, b))
    M = int(input())
    uvs = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

    e2Roots = [set() for _ in range(N)]
    def dfs(vNow, vPar):
        for v2 in adjL[vNow]:
            if v2 == vPar: continue
            e2Roots[v2] |= e2Roots[vNow]
            e2Roots[v2].add((vNow, v2))
            dfs(v2, vNow)

    dfs(0, -1)

    ePaths = [set() for _ in range(M)]
    for i, (u, v) in enumerate(uvs):
        ePaths[i] = e2Roots[u] ^ e2Roots[v]

    numEs = [0] * (1<<M)
    for a, b in edges:
        ptn = 0
        for iC, ePath in enumerate(ePaths):
            if (a, b) in ePath or (b, a) in ePath:
                ptn |= 1<<iC
        for S in range(1<<M):
            if S & ptn:
                numEs[S] += 1

    def getPows(base, n):
        pows = [1] * (n+1)
        for x in range(1, n+1):
            pows[x] = (pows[x-1] * base)
        return pows
    pows = getPows(2, N)

    def getNum1s(N):
        num1s = [0]
        for _ in range(N):
            num12s = [num1+1 for num1 in num1s]
            num1s += num12s
        return num1s
    num1s = getNum1s(M)

    ans = pows[N-1]
    for S in range(1, 1<<M):
        num = pows[N-1-numEs[S]]
        if num1s[S] % 2:
            ans -= num
        else:
            ans += num

    print(ans)


solve()

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)
M = int(input())
AB = tuple(tuple(map(int, input().split())) for _ in range(M))


parent = [-1] * (N + 1)
node = [1]
while node:
    s = node.pop()
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

pair = [-1] * M
for i, (a, b) in enumerate(AB):
    pa = set()
    pb = set()
    while a != 1:
        pa.add(a - 1)
        a = parent[a]
    while b != 1:
        pb.add(b - 1)
        b = parent[b]
    pair[i] = pa ^ pb

ans = pow(2, N - 1)

whole = set(range(1, N))
for bit in range(1, 1 << M):
    popcnt = 0
    inter = set()
    for i in range(M):
        if (bit >> i) & 1:
            popcnt += 1
            inter |= pair[i]
    x = N - len(inter) - 1
    if popcnt % 2 == 1:
        ans -= 2 ** x
    else:
        ans += 2 ** x

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N=int(input())
P=[[] for i in range(N+1)]
Side=[0 for i in range(N-1)]
for i in range(N-1):
    a,b=map(int,input().split())
    Side[i]=[a,b]
    P[a].append(b)
    P[b].append(a)

global deep
deep=[-1 for i in range(N+1)]
deep[1]=0
st=[1]
while st:
    s=st.pop()
    for i in P[s]:
        if deep[i]==-1:
            st.append(i)
            deep[i]=deep[s]+1

global Path
M=int(input())
Path=[]

def Proc(u):
    for j in P[u]:
        if deep[j]<deep[u]:
            if not [j,u] in Path:
                Path.append([j,u])
            return j
        
UV=[]
for i in range(M):
    u,v=map(int,input().split())
    UV.append([u,v])

C=0
sym=1
for i in range(1,M+1):
    for comb in combinations(UV,i):
        Path=[]
        for j in range(i):
            u,v=comb[j]
            while True:
                if u==v:
                    break
                if deep[u]>deep[v]:
                    u=Proc(u)
                elif deep[u]<deep[v]:
                    v=Proc(v)   
                elif deep[u]==deep[v]:
                    u=Proc(u)
                    v=Proc(v)
        C+=sym*2**(N-1-len(Path))
    sym*=-1
ans=2**(N-1)-C
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

class Node:
    
    def __init__(self, num):
        self.num = num
        self.depth = 0
        self.parent = (None, None)


LI = lambda: list(map(int, input().split()))

# input
N = int(input())
AB = [LI() for _ in range(N - 1)]
M = int(input())
UV = [LI() for _ in range(M)]

# params
links = [[] for _ in range(N)]
nodes = [Node(i) for i in range(N)]
w = []
p2 = [2 ** i for i in range(N + 1)]


def create_links():
    for i in range(N - 1):
        a, b = AB[i][0] - 1, AB[i][1] - 1
        links[a].append((b, i))
        links[b].append((a, i))


def create_tree(v, p=-1):
    for u, i in links[v]:
        if u == p:
            continue
        nodes[u].parent = (nodes[v], i)
        nodes[u].depth = nodes[v].depth + 1
        create_tree(u, v)


def between_links(s, t):
    x = nodes[s]
    y = nodes[t]
    if x.depth > y.depth:
        x, y = y, x
    s = set()
    while x.depth < y.depth:
        y, i = y.parent
        s.add(i)
    while x is not y:
        x, i = x.parent
        y, j = y.parent
        s.add(i)
        s.add(j)
    return s


def create_between_links():
    for u, v in UV:
        s = between_links(u - 1, v - 1)
        w.append(s)


def main():
    create_links()
    create_tree(0)
    create_between_links()
    
    ans = p2[N - 1]
    l = [(set(), 0)]
    for s1 in w:
        ll = list(l)
        for s2, n in ll:
            s = s1 | s2
            d = p2[N - 1 - len(s)]
            n += 1
            if n % 2 == 0:
                ans += d
            else:
                ans -= d
            l.append((s, n))
    print(ans)

    
if __name__ == "__main__":
    main()