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(10000000)
input = sys.stdin.readline
from math import log
from collections import *

class LCA:

    def __init__(self, N, root, es):
        self.N = N
        self.root = root
        self.es = es
        self.LOG_N = LOG_N = int(log(N, 2)) + 1
        self.parent = [[-1 for _ in range(N)] for _ in range(LOG_N)]
        self.depth = [0 for _ in range(N)]
        self.dfs(root, -1, 0)
        parent = self.parent
        for k in range(LOG_N-1):
            for v in range(N):
                if parent[k][v] < 0:
                    parent[k+1][v] = -1
                else:
                    parent[k+1][v] = parent[k][parent[k][v]]
        self.parent = parent

    def dfs(self, v, p, d):
        self.parent[0][v] = p
        self.depth[v] = d
        for u in self.es[v]:
            if u != p:
                self.dfs(u, v, d+1)

    def lca(self, u, v):
        LOG_N = self.LOG_N
        depth = self.depth
        parent = self.parent
        if depth[u] > depth[v]:
            t, u = u, v
            v = t
        for k in range(LOG_N):
            if (depth[v] - depth[u]) >> k & 1:
                v = parent[k][v]
        if u == v:
            return u
        for k in range(LOG_N)[::-1]:
            if parent[k][u] != parent[k][v]:
                u, v = parent[k][u], parent[k][v]
        return parent[0][u]

N = int(input())
edges = [[] for i in range(N)]
edge_id = defaultdict(lambda : -1)
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)
    edge_id[(a, b)] = edge_id[(b, a)] = i
path_from_root = [0] * N
visited = [0] * N

def set_path(v, path):
    visited[v] = 1
    path_from_root[v] = path
    for u in edges[v]:
        if visited[u] == 0:
            set_path(u, path | (1 << edge_id[(v, u)]))

set_path(0, 0)
M = int(input())
uv = [list(map(lambda x: int(x)-1, input().split())) for i in range(M)]
tree = LCA(N, 0, edges)
popcount = lambda s: bin(s).count('1')
ans = pow(2, N-1)
for i in range(1, 1 << M):
    all_path = 0
    for j in range(M):
        if i & (1 << j):
            u, v = uv[j][0], uv[j][1]
            l = tree.lca(u, v)
            path = (path_from_root[u] | path_from_root[v]) & ~path_from_root[l]
            all_path |= path
    if popcount(i) & 1:
        ans -= pow(2, N-1-popcount(all_path))
    else:
        ans += pow(2, N-1-popcount(all_path))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  def popcount(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
              
  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = popcount(i) % 2
    ans += (-1)**cnt * 2**(n-1-popcount(s))
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      f = True
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        f = False
        break
      if f:
        stack.pop()

  E = [set() for _ in range(m)]
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i].add((min(edge[j], edge[j+1]), max(edge[j], edge[j+1])))

  ans = 0
  for i in range(2**m):
    s = set()
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = bin(i).count("1") % 2
    ans += (-1)**cnt * 2**(n-1-len(s))
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

def dfs(u, v):
  parent = [-1]*n
  seen = [False]*n
  stack = [u]
  seen[u] = True
  while stack:
    nv = stack[-1]
    if nv == v:
      return stack
    f = True
    for i in T[nv]:
      if seen[i]:
        continue
      stack.append(i)
      seen[i] = True
      f = False
      break
    if f:
      stack.pop()

E = [set() for _ in range(m)]
for i in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  edge = dfs(u, v)
  for j in range(len(edge)-1):
    E[i].add((min(edge[j], edge[j+1]), max(edge[j], edge[j+1])))

ans = 0
for i in range(2**m):
  s = set()
  for j in range(m):
    if i>>j & 1:
      s |= E[j]
  cnt = bin(i).count("1") % 2
  ans += (-1)**cnt * 2**(n-1-len(s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
    
    root = 0
    q = []
    q.append(root)
    pre = [-1]*N
    visited = [False]*N
    while q:
        v = q.pop() 
        visited[v] = True
        for to in edge[v]:
            if visited[to]:
                continue
            pre[to] = v
            q.append(to)
    
    path = [] #パスに含まれる辺(根に向かう方で保存)
    constraint = []
    M=I()
    for i in range(M):
        a,b = MI_()
        constraint.append((a,b))
        root_path_a = set()
        root_path_b = set()
        while a!=root:
            root_path_a.add((a,pre[a]))
            a = pre[a]
        while b!=root:
            root_path_b.add((b,pre[b]))
            b = pre[b]
        path.append(root_path_a ^ root_path_b) #LCAまでのみ
    

    ans = 0
    for mask in range(1<<M):
        builtin_count = 0
        U = set() #pathに含まれる辺
        for i in range(M):
            if mask>>i&1:
                builtin_count += 1
                U |= path[i]
        if builtin_count&1:
            ans -= 1<<(N-1-len(U))
        else:
            ans += 1<<(N-1-len(U))
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n = int(input())
    edge = []
    edge_id = []
    for i in range(n):
        edge.append([])
        edge_id.append(dict())
    for i in range(n-1):
        a, b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        edge_id[a-1].update({b-1: i})
        edge_id[b-1].update({a-1: i})
    m = int(input())
    uv = []
    for i in range(m):
        uv.append(list(map(int, input().split())))

    edge_mask = []
    for i in range(m):
        distance_from_u = []
        visited = []
        for j in range(n):
            distance_from_u.append(0)
            visited.append(False)
        que = deque()
        que.append([uv[i][0]-1, 0])
        while len(que) > 0:
            now, dist = que.popleft()
            if visited[now]:
                continue
            visited[now] = True
            distance_from_u[now] = dist
            for x in edge[now]:
                if not visited[x]:
                    que.append([x, dist+1])
        next = uv[i][1]-1
        edge_set = set()
        while distance_from_u[next] > 0:
            for x in edge[next]:
                if distance_from_u[x] < distance_from_u[next]:
                    edge_set.add(edge_id[next][x])
                    next = x
                    break
        edge_mask.append(edge_set)

    dp_mask = []
    for i in range(n-1):
        new_mask = 0
        for j in range(m):
            if i in edge_mask[j]:
                new_mask = new_mask | (1 << j)
        dp_mask.append(new_mask)

    dp = []
    for i in range(n):
        dp.append([])
        for j in range(1 << m):
            dp[i].append(0)
    dp[0][0] = 1
    for i in range(n-1):
        for j in range(1 << m):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j|dp_mask[i]] += dp[i][j]

    ans = dp[n-1][(1<<m)-1]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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)
        if a > b:
            a, b = b, a
        edges.append((a, b))
    M = int(input())
    uvs = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

    def getPath(vSt, vEn):
        def dfs(vNow, vPar):
            if vNow == vEn:
                path.append(vNow)
                return True
            for v2 in adjL[vNow]:
                if v2 != vPar:
                    if dfs(v2, vNow):
                        path.append(vNow)
                        return True
        path = []
        dfs(vSt, -1)
        return path

    edgeConstraints = []
    for u, v in uvs:
        path = getPath(u, v)
        setEdge = set()
        for j in range(len(path)-1):
            a, b = path[j], path[j+1]
            if a > b:
                a, b = b, a
            setEdge.add((a, b))
        edge = 0
        for j, (a, b) in enumerate(edges):
            if (a, b) in setEdge:
                edge |= 1<<j
        edgeConstraints.append(edge)

    numEs = []
    for S in range(1<<M):
        edge = 0
        for i, edgeConstraint in enumerate(edgeConstraints):
            if (S>>i) & 1:
                edge |= edgeConstraint
        numE = bin(edge).count('1')
        numEs.append(numE)

    pow2s = [1]
    for i in range(N):
        pow2s.append(pow2s[-1]*2)

    ans = 0
    for S, numE in enumerate(numEs[1:], 1):
        num1 = bin(S).count('1')
        if num1 % 2:
            ans += pow2s[N-1-numE]
        else:
            ans -= pow2s[N-1-numE]

    print(pow2s[N-1] - ans)


solve()

Submission status: Time Limit Exceeded

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


def get_path(u, v):
    stack = [u]
    prev = [None] * (N+1)
    visited = [False] * (N+1)
    visited[u] = True
    while stack:
        node = stack.pop()
        for next, i in G[node]:
            if not visited[next]:
                visited[next] = True
                prev[next] = (node, i)
                stack.append(next)
    path = 0
    node = v
    while node != u:
        p, i = prev[node]
        node = p
        path += 1 << i
    return path


def count(bits, N):
    cnt = 0
    for i in range(N):
        if ((bits >> i) & 1) == 1:
            cnt += 1
    return cnt


M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]
paths = [get_path(u, v) for u, v in uv]
ans = 2**(N-1)
for bit in range(1, 1 << M):
    cnt = 0
    tmp = 0
    for i in range(M):
        if ((bit >> i) & 1) == 1:
            cnt += 1
            tmp |= paths[i]
    ans += (-1)**cnt * 2**(N-1-count(tmp, N-1))
print(ans)

Submission status: Time Limit Exceeded

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


def get_path(u, v):
    stack = [u]
    prev = [-1] * (N+1)
    visited = [False] * (N+1)
    visited[u] = True
    while stack:
        node = stack.pop()
        for next in G[node]:
            if not visited[next]:
                visited[next] = True
                prev[next] = node
                stack.append(next)
    path = [v]
    node = v
    while node != u:
        p = prev[node]
        path.append(p)
        node = p
    return path[::-1]


def get_size(paths):
    edges = set()
    for path in paths:
        for i in range(len(path)-1):
            u = path[i]
            v = path[i+1]
            if u > v:
                u, v = v, u
            edges.add((u, v))
    return len(edges)


M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]
paths = [get_path(u, v) for u, v in uv]
ans = 2**(N-1)
for bit in range(1, 1 << M):
    cnt = 0
    tmp = []
    for i in range(M):
        if ((bit >> i) & 1) == 1:
            cnt += 1
            tmp.append(paths[i])
    x = get_size(tmp)
    ans += (-1)**cnt * 2**(N-1-get_size(tmp))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def popcount(i):
    return bin(i).count('1')

def dfs(i, N, nodes, src, dest):
    """ DFS(木、再帰、重みなし) """

    dist = [INF] * N
    def rec(u, prev, c):
        if u == dest:
            return True
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                if rec(v, u, c+1):
                    # 目的の頂点に到達したら、それに至る辺集合をbitで持っておく
                    A[i] |= 1 << edges[(u, v)]
                    return True
        return False
    rec(src, -1, 0)

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = i
    edges[(b, a)] = i

M = INT()
# A[i] := 条件iで白くしなければいけない辺の集合
A = [0] * M
for i in range(M):
    u, v = MAP()
    u -= 1; v -= 1
    dfs(i, N, nodes, u, v)

# 全通り数から、包除原理に基づいて足し引きしていく
ans = 2 ** (N-1)
for S in range(1, 1<<M):
    # Sで表される条件の集合において、白くしなければならない辺の集合S2
    S2 = 0
    for i in range(M):
        if S & 1<<i:
            S2 |= A[i]
    # 白くしなければならない辺の数
    edgecnt = popcount(S2)
    # 今回の状態Sを作るパターンの通り数(2^白黒自由に選べる辺の数)
    cnt = 2**(N-1-edgecnt)
    if popcount(S) % 2 == 1:
        ans -= cnt
    else:
        ans += cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


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

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    ANS=[y]
    while y!=x:
        y=USE[y]
        ANS.append(y)

    RET=[]

    for i in range(1,len(ANS)):
        RET.append(DICT[tuple(sorted([ANS[i-1],ANS[i]]))])

    return set(RET)

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

for i in range(N-1):
    B=0
    for k in range(M):
        if i in Q2[k]:
            B+=1<<k
        
    for j in range((1<<M)-1,-1,-1):
        DP[j|B]+=DP[j]

print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

DICT={x:ind for ind,x in enumerate(E)}

EDGE=[[] for i in range(N+1)]
for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)


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

def dfs(x,y):
    USE=[-1]*(N+1)
    USE[x]=0

    NOW=[x]

    while NOW:
        n=NOW.pop()

        for to in EDGE[n]:
            if USE[to]==-1:
                USE[to]=n
                NOW.append(to)

    ANS=[y]
    while y!=x:
        y=USE[y]
        ANS.append(y)

    RET=[]

    for i in range(1,len(ANS)):
        RET.append(DICT[tuple(sorted([ANS[i-1],ANS[i]]))])

    return set(RET)

Q2=[dfs(x,y) for x,y in Q]

DP=[0]*(1<<M)
DP[0]=1

import copy
for i in range(N-1):
    NDP=copy.deepcopy(DP)
    B=0
    for k in range(M):
        if i in Q2[k]:
            B+=1<<k
        
    for j in range(1<<M):
        NDP[j|B]+=DP[j]

    DP=NDP

print(DP[-1])

Submission status: Time Limit Exceeded

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

n = int(input())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
m = int(input())
uv = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]

e = [[] for _ in range(n)]
i = 0
for a, b in ab:
    e[a].append([b, i])
    e[b].append([a, i])
    i += 1

def func(x, g, p):
    #print(x, g, p, e[x])
    if len(e[x]) == 1 and p != -1:
        return -1
    for edge in e[x]:
        if edge[0] == p:
            continue
        elif edge[0] == g:
            #print(edge)
            return 1 << edge[1]
        temp = func(edge[0], g, x)
        #print(temp, x, g, p)
        if temp >= 0:
            #print(edge[1])
            return temp + (1 << edge[1])
    return -1

p = []
for u, v in uv:
    p.append(func(u, v, -1))

#print(p)
flag = -1
ans = 2 ** (n-1)
#print(ans)
base = 2 ** (n-1)
for i in range(1, 1 << m):
    temp = list(reversed(list(str(bin(i)))[2:]))
    c = 0
    #print(temp)
    for j, x in enumerate(temp):
        if x == '1':
            c = c | p[j]
    #print(bin(base + c))
    hoge = str(bin(base + c)).count('0') - 1
    if temp.count('1') % 2 == 0:
        flag = 1
    else:
       flag = -1
    ans += flag * (2 ** hoge)
    #flag *= -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
E = [[int(l) for l in input().split()] for _ in range(N-1)]
M = int(input())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

C = [set([]) for _ in range(M)]
for i in range(N-1):
    uf = UnionFind(N)
    for e in E:
        if e == E[i]:
            continue
        uf.unite(e[0], e[1])
    for l in range(M):
        if uf.isSameGroup(L[l][0], L[l][1]):
            continue
        C[l].add(i)

import itertools

ans = 0
L = [int(i) for i in range(M)]
for m in range(M+1):
    for P in itertools.combinations(L, m):
        white = set([])
        for j in P:
            white = white | C[j]
        if m%2:
            ans -= 1 << N-1-len(white)
        else:
            ans += 1 << N-1-len(white)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
E = [[int(l) for l in input().split()] for _ in range(N-1)]
M = int(input())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

C = [set([]) for _ in range(M)]
for i in range(N-1):
    uf = UnionFind(N)
    for e in E:
        if e == E[i]:
            continue
        uf.unite(e[0], e[1])
    for l in range(M):
        if uf.isSameGroup(L[l][0], L[l][1]):
            continue
        C[l].add(i)

ans = 0
for i in range(2**M):
    cnt = 0
    white = set([])
    for j in range(M):
        if i & 1 << j:
            cnt += 1
            white = white | C[j]
    if cnt%2:
        ans -= pow(2, N-1-len(white))
    else:
        ans += pow(2, N-1-len(white))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
E = [[int(l) for l in input().split()] for _ in range(N-1)]
M = int(input())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

C = [set([]) for _ in range(M)]
for i in range(N-1):
    uf = UnionFind(N)
    for e in E:
        if e == E[i]:
            continue
        uf.unite(e[0], e[1])
    for l in range(M):
        if uf.isSameGroup(L[l][0], L[l][1]):
            continue
        C[l].add(i)

ans = 0
for i in range(2**M):
    cnt = 0
    white = set([])
    for j in range(M):
        if i & 1 << j:
            cnt += 1
            white = white | C[j]
    if cnt%2:
        ans -= 2**(N-1-len(white))
    else:
        ans += 2**(N-1-len(white))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
from collections import deque
list1 = []
for i in range(N-1): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m] #1列の数列をリスト化
    list1.append(q)
l = [[] for i in range(N+1)]
for pi in list1:  #0-originedに注意
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
sousa = deque([[1,0,0]]) #[捜査対象ノード,親ノード,そのノードの距離](今1を頂点とする木を作る)
node = [[] for i in range(N)] #n番目のリストにn+1について[親ノード,rootからの距離,子ノード]
while len(sousa) != 0:
    a = sousa.popleft()
    b = l[a[0]]
    if a[1]!=0:
        b.remove(a[1])
    if len(b) == 0:
        pass
    else:
        for i in b:
            sousa.append([i,a[0],a[2]+1])
    node[a[0]-1] = [a[1]] + [a[2]] + b
u = 0
M = int(input())
list2 = []
for i in range(M): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m] #1列の数列をリスト化
    list2.append(q)
road = []
for i in list2:
    aproad = []
    ls = i[0]
    rs = i[1]
    if node[ls-1][1] > node[rs-1][1]:
        while node[ls-1][1] != node[rs-1][1]:
            aproad = aproad + [min(ls,node[ls-1][0])*100 + max(ls,node[ls-1][0])]
            ls = node[ls-1][0]
    elif node[ls-1][1] < node[rs-1][1]:
        while node[ls-1][1] != node[rs-1][1]:
            aproad = aproad + [min(rs,node[rs-1][0])*100 + max(rs,node[rs-1][0])]
            rs = node[rs-1][0]

    while True:
        if ls == rs:
            break
        aproad = aproad + [min(ls,node[ls-1][0])*100 + max(ls,node[ls-1][0])]
        aproad = aproad + [min(rs,node[rs-1][0])*100 + max(rs,node[rs-1][0])]
        ls = node[ls-1][0]
        rs = node[rs-1][0]
    
    road.append(aproad)
roadgun = []
A = int("0",2)
for i in range(2**M-1):
    k = i+1
    kstr = bin(k)
    if kstr.count("1") == 1:
        roadgun.append(road[len(kstr)-3])
        A = A + int("1"+"0"*(N-(len(roadgun[-1]))-1),2)

    else:
        set1 = set(road[len(kstr)-3])
        set2 = set(roadgun[int(kstr[3:],2)-1])
        set3 = set1.union(set2)
        roadgun.append(list(set3))
        if kstr.count("1")%2 == 1:
            A = A + int("1"+"0"*(N-(len(roadgun[-1]))-1),2)
        else:
            A = A - int("1"+"0"*(N-(len(roadgun[-1]))-1),2)
  
A = int("1"+"0"*(N-1),2) - A
print(A)

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 lb, u in links[v]:
            if u in visited:
                continue
            q.append((u, used | lb))


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


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
    lb = 1 << i
    links[a].add((lb, b))
    links[b].add((lb, 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 = bitcount64(i)
    bit = 0
    k = i
    while k:
        b = k & -k
        j = b.bit_length() - 1
        bit |= conditions[j]
        k ^= b
    free_link_cnt = n - 1 - bitcount64(bit)
    val = 2 ** free_link_cnt
    if cnd_cnt % 2:
        ans -= val
    else:
        ans += val
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  N = int(input())
  E = [[] for _ in range(N)]
  for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append((b,i))
    E[b].append((a,i))
  
  EG = []
  def dfs(u,v,p):
    if u == v:
      return True
    for t,i in E[u]:
      if t == p:
        continue
      if dfs(t,v,u):
        EG.append(i)
        return True
    return False
  
  M = int(input())
  EM = []
  for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    EM.append((u,v))
  
  ans = 0
  for i in range(1<<M):
    EG2 = []
    bc = 0
    for j in range(M):
      if (i>>j)&1 == 1:
        bc += 1
        u,v = EM[j]
        EG = []
        dfs(u,v,-1)
        EG2 += EG
    p = len(set(EG2))
    if bc%2 == 0:
      ans += 2**(N-1-p)
    else:
      ans -= 2**(N-1-p)
  print(ans)

if __name__ == '__main__':
  main()