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: Wrong Answer

Solution code:
from collections import deque,defaultdict

N=int(input())
G=[[] for _ in range(N)]

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

def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev
  
M = int(input())
path_list=[0]*M
for i in range(M):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  d,prev = bfs(u)
  path=[v]
  for j in range(d[v]):
    prev_v = prev[v]
    path.append(prev_v)
    v = prev_v
  path_list[i] = path
  
count=defaultdict(int)
for path in path_list:
  for i in range(len(path)-1):
    a,b = path[i],path[i+1]
    a,b = sorted((a,b))
    count[(a,b)] += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def popcnt(x):
    c = 0
    while x>0:
        c += x%2
        x >>= 1
    return c

def dfs(u,v,p):
    global d
    d[u][v] = p
    for x in dst[v]:
        if u!=x and d[u][x]==0:
            p |= 1<<dst[v][x]
            dfs(u,x,p)
            p ^= 1<<dst[v][x]

n = inn()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    a,b = inm()
    dst[a][b] = dst[b][a] = i

m = inn()
u = []
v = []
for i in range(m):
    uu,vv = inm()
    u.append(uu)
    v.append(vv)

if True and n==2 and m==1:
    print(0)
    exit()

d = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    dfs(i,i,0)
dd = []
for i in range(m):
    dd.append(d[u[i]][v[i]])
ddprint(dst)
ddprint(d)
ddprint(u)
ddprint(v)
ddprint(dd)

y = 0
for i in range(1,2**m):
    nbits = x = 0
    for j in range(m):
        if (i>>j)%2>0:
            x |= dd[j]
            nbits += 1
    nsegs = popcnt(x)
    s = 2*(nbits%2)-1
    y += s*2**(n-1-nsegs)
print(2**(n-1)-y)

Submission status: Wrong Answer

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,1<<u))
  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
            que.append((i,L|1<<i))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = 0
    l = 0
    for k in j:
      p = all_bit_count(K)
      f = all_bit_count(k)
      K |= k
      B = all_bit_count(K)
      if f+p == B:
        l += f-1
      else:
        l = B-1
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Submission status: Wrong Answer

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(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

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,1<<u))
  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
            que.append((i,L|1<<i))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = 0
    l = 0
    for k in j:
      p = all_bit_count(K)
      f = all_bit_count(k)
      K |= k
      B = all_bit_count(K)
      if f+p == B:
        l += f-1
      else:
        l = B-1
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列


    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        for i, (a, b) in enumerate([map(int, input().split()) for i in range(N-1)]):#木じゃない場合N-1をNに変える
            edgelist[a-1].append((b-1,i))#ノードの番号が0から始まる場合-1を消す
            edgelist[b-1].append((a-1,i))
        return edgelist
    edge=tree_init(N)
    M = int(input())
    ms= tuple(tuple(map(int, input().split())) for i in range(M))
    ways=[]

    for u,v in ms:
        u-=1;v-=1
        q=deque([(u,"")])
        visited=[False]*N
        while q:
            x=q.pop()#ここをpopleftにすると幅優先探索BFSになる
            #print(x)
            e,way=x
            if visited[e]:continue
            if e==v:
                ways.append(set(map(int, way)))
            visited[e]=True
            for ne, j in edge[e]:
                q.append((ne,way+str(j)))
    #print(ways)
    tot=pow(2,N-1)
    for i in range(1,M+1):
        for ws in combinations(ways,i):
            ts=set()
            for w in ws:
                ts|=w
            tot+=(-1)**i*pow(2,N-1-len(ts))
    print(tot)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))



def solve():
  N = ni()
  G = [list() for _ in range(N)]
  for _ in range(n-1):
      u, v = nm()
      u -= 1; v -= 1
      G[u].append(v)
      G[v].append(u)

  S = []
  F = [0]*N
  elt = list()
  par = [0-1]*N
  depth = [0]*N
  def dfs(v, d):
      F[v] = len(S)
      elt.append(v)
      depth[v] = d
      S.append(v)
      for w in G[v]:
          if w == par[v]:
              continue
          par[w] = v
          dfs(w, d+1)
          S.append(v)
  dfs(0, 0)

  INF = (N, None)

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

  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

  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]]
  
  m = ni()
  task = [tuple(nm()) for _ in range(m)]
  lca = [0]*m
  for i in range(m):
    lca[i] = query(*task[i])
  ans = [0]*(1<<m)
  for bit in range(1<<m):
    tree = [0]*n
    for i in range(m):
      if bit & (1<<i):
        u, v = task[i]
        p = lca[i]
        if depth[u] < depth[v]:
          u, v = v, u

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

################################

n = ni()
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    a,b = na()
    cost[a-1][b-1] = 1
    cost[b-1][a-1] = 1

dp = set()
m = ni()
for i in range(m):
    u,v = na()
    d = dijkstra_back(u-1,v-1,n,n-1,cost)
    for j in range(len(d)-1):
        a,b = min(d[j],d[j+1]),max(d[j],d[j+1])
        dp.add((a,b))

a = len(dp)
print(2**(n-1)-2**(n-1-a))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

################################

n = ni()
cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(n-1):
    a,b = na()
    cost[a-1][b-1] = 1
    cost[b-1][a-1] = 1

dp = set()
m = ni()
for i in range(m):
    u,v = na()
    d = dijkstra_back(u-1,v-1,n,n-1,cost)
    for j in range(len(d)-1):
        a,b = min(d[j],d[j+1]),max(d[j],d[j+1])
        dp.add((a,b))

a = len(dp)
print(2**n-2**(n-1-a))

Submission status: Wrong Answer

Solution code:
def main():
    from functools import reduce
    from itertools import combinations

    def bit_path(u, v, bit=0):
        if u == v:
            return bit

        for i, e in enumerate(es):
            if (bit >> i) & 1: continue
            if u not in e: continue
            res = bit_path(sum(e) - u, v, bit | (1 << i))
            if res:
                return res

    N = int(input())

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

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    def a_or_b(a, b):
        return a | b

    ans = 1 << (N - 1)
    for k in range(1, N):
        for comb in combinations(cons, r=k):
            b = reduce(a_or_b, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - bin(b).count('1')))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def main():
    from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
    N = int(input())
    G = [[-1]*N for i in range(N)]

    def get_path(start, goal, pred):
        return get_path_row(start, goal, pred[start])

    def get_path_row(start, goal, pred_row):
        path = []
        i = goal
        while i != start and i >= 0:
            path.append(i)
            i = pred_row[i]
        if i < 0:
            return []
        path.append(i)
        return path[::-1]

    ans = 2**(N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a][b] = i
        G[b][a] = i
    G2 = csgraph_from_dense(G, null_value=-1)
    g, p = floyd_warshall(G2, return_predecessors=True)
    ans = 0
    # print(g)
    M = int(input())
    s = [0 for i in range(M)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        gp = get_path(u, v, p)
        for j in range(len(gp)-1):
            s[i] |= 1 << G[gp[j]][gp[j+1]]

    # print(s)
    for i in range(2**M):
        tmp = 2**(N-1) - 1
        c = 0
        for j in range(M):
            if (i >> j) % 2 == 1:
                tmp &= ~s[j]
                c += 1
        ans += ((-1)**(c))*(1 << popcount(tmp))

    print(ans)


main()

Submission status: Wrong Answer

Solution code:

class Graph(object):
    def __init__(self, n: int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def add_edge(self, v1: int, v2: int, undirected=False):
        self.adjacency_dict[v1].append(v2)
        if undirected:
            self.adjacency_dict[v2].append(v1)

    def dfs_init(self, u, v):
        self.visited = [False] * self.n
        self.found = False
        # self.res = [0] * self.n
        self.res = 0
        self.dfs(u, v)
        return self.res

    def dfs(self, u, v):
        if u == v:
            self.found = True
            self.res += 1 << u
            return

        self.visited[u] = True
        for child in self.adjacency_dict[u]:
            if not self.visited[child]:
                self.dfs(child, v)
            if self.found:
                break

        if self.found:
            self.res += 1 << u


N = int(input())
g = Graph(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    g.add_edge(a-1, b-1, undirected=True)

M = int(input())
constraint = {}
for m in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    constraint[m] = g.dfs_init(u, v)
# print(constraint)


def calc_combi(m, constraint):
    # M個中m(001101101)の制約を全て満たす組み合わせの数を計算する
    temp = 0
    cnt = 0
    for i in range(m.bit_length()):
        if (m >> i & 1) == 1:
            temp = temp | constraint[i]
            cnt += 1
    return temp, cnt


# 包除原理で計算していく
ans = pow(2, N-1)
for m in range(1, 2**M):
    res, cnt = calc_combi(m, constraint)

    if cnt % 2 == 0:
        ans += pow(2, N - bin(res).count('1'))
    else:
        ans -= pow(2, N - bin(res).count('1'))

'''
for m in list(itertools.product([0,1], repeat=M)):
    if sum(m) == 0:
        continue
    if sum(m) % 2 == 0:
        ans += calc_combi(m, constraint)
    else:
        ans -= calc_combi(m, constraint)
'''

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# F
# 条件を満たさないものを考えていき、包除原理を使う
# DFSでsからtまでの辿る辺をまず持っておく
# itertoolのproduct使うと便利

import itertools

'''
3
1 2
2 3
1
1 3
'''


class Graph(object):
    def __init__(self, n: int):
        """ ノードのつながりを辞書型で表現する
        要素数nであり、要素は0からn-1である想定
        >> - usage
        g = Graph(n=n)

        """
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def add_edge(self, v1: int, v2: int, undirected=False):
        self.adjacency_dict[v1].append(v2)
        if undirected:
            self.adjacency_dict[v2].append(v1)

    def dfs_init(self, u, v):
        self.visited = [False] * self.n
        self.found = False
        self.res = []
        self.dfs(u, v)
        return self.res

    def dfs(self, u, v):
        if u == v:
            self.found = True
            self.res.append(u)
            return

        self.visited[u] = True
        for child in self.adjacency_dict[u]:
            if not self.visited[child]:
                self.dfs(child, v)
            if self.found:
                break

        if self.found:
            self.res.append(u)


N = int(input())
g = Graph(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    g.add_edge(a-1, b-1, undirected=True)
# print(g.adjacency_dict)

M = int(input())
constraint = {}
for m in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    constraint[m] = g.dfs_init(u, v)
    # res.append(pow(2, N - len(constraint[m])))
# print(constraint)


def calc_combi(m, constraint):
    # M個中m(001101101)の制約を全て満たす組み合わせの数を計算する
    s = set([])
    for idx, i in enumerate(m):
        if i == 1:
            s = s | set(constraint[idx])
    ret = pow(2, N - len(s))
    # print(m, s, ret)
    return ret


ans = pow(2, N-1)
# 包除原理
for m in list(itertools.product([0,1], repeat=M)):
    if sum(m) == 0:
        continue
    if sum(m) % 2 == 0:
        ans += calc_combi(m, constraint)
    else:
        ans -= calc_combi(m, constraint)

print(ans)

Submission status: Wrong Answer

Solution code:
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)]
route = [[] for _ in range(N)]

for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    route[a].append((b, i))
    route[b].append((a, i))

path = [0] * M
for i, (u, v) in enumerate(uv):
    u -= 1
    v -= 1
    stack = [u]
    visited = [0] * N
    visited[u] = 1
    dire = [[] for _ in range(N)]
    while True:
        s = stack.pop()
        for g, j in route[s]:
            if visited[g]:
                continue   
            stack.append(g)
            dire[g].append((s, j))
            visited[g] = 1
        if visited[v]:
            break
    s = v
    while True:
        g, num = dire[s][0]
        path[i] |= (1 << num)
        if g == u:
            break

data = [0] * (1 << M)
ans = 2 ** (N - 1)
for i in range(1, a << M):
    k = bin(i) - 3
    data[i] = data[i - (2 ** k)] | path[k]
    power = bin(data[i]).count("1")
    judge = bin(i).count("1")
    ans += (-2 ** (N - 1 - power) if judge % 2 else 2 ** (N - 1 - power))
print(ans)

Submission status: Wrong Answer

Solution code:
# 多分TLE
from scipy.sparse.csgraph import dijkstra
from itertools import combinations

N = int(input())
edge_id = {}
D = [[-float('inf')]*N for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1][b-1] = D[b-1][a-1] = 1
  edge_id[(a-1, b-1)] = i
  edge_id[(b-1, a-1)] = i

paths = dijkstra(D, return_predecessors=True)[1]
M = int(input())
edges = [0] * M
for i in range(M):
  u, v = map(int, input().split())
  now, p = paths[u-1][v-1], v-1
  edges[i] += 1 << edge_id[(now, p)]
  while now != u-1:
    now, p = paths[u-1][now], now
    edges[i] += 1 << edge_id[(now, p)]

ans = pow(2, N-1)
for m in range(1, M+1):
  coeff = -1
  for comb in combinations(edges, m):
    e = 0
    for c in comb:
      e |= c
    ans += coeff * pow(2, N-1-bin(e).count('1'))
    coeff *= -1

print(ans)

Submission status: Wrong Answer

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

import numpy as np

MOD = 10 ** 9 +7

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 i ,(a,b) in enumerate(ab):
    graph[a].append((b,i))
    graph[b].append((a,i))

def get_path(u,v):
    INF = 100
    visited =[False]*(n+1)
    pred =[None]*(n+1)
    stack =[u]
    visited[u]=True
    while stack:
        v = stack.pop()
        for w,i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v,i)
            stack.append(w)
    path = 0
    w = v
    while w!= u:
        v,i = pred[w]
        w =v
        path+=1<<i
    return path

condition_path = [get_path(u,v)for u,v in uv]

s=np.zeros(1<<m,np.int64)
sgn = np.ones(1<<m,np.int64)
for i in range(m):
    s[1<<i:1<<(i+1)] = s[:1<<i] | condition_path[i]
    sgn[1<<i:1<<(i+1)]=-sgn[:1<<i]

def popcnt(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_edges = popcnt(s)

x= 1<<(n-1-n_edges)
answer =(x*sgn).sum()
print(answer)
#maspyさんのコードをほぼ写経しました。すみません。(+_+)

Submission status: Wrong Answer

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):
    print(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: Wrong Answer

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 len(white) == N-1:
            break
    if cnt%2:
        ans -= 1 << N-1-len(white)
    else:
        ans += 1 << N-1-len(white)
print(ans)

Submission status: Wrong Answer

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 (M-cnt)%2:
        ans += 2**(N-1-len(white))
    else:
        ans -= 2**(N-1-len(white))
print(ans)

Submission status: Wrong Answer

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-M)%2:
        ans -= 2**(N-1)-2**(N-1-len(white))
    else:
        ans += 2**(N-1)-2**(N-1-len(white))
print(ans)

Submission status: Wrong Answer

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

from fractions import gcd
from functools import reduce

# functions
def lcm(x, y):
    if x % y == 0:
        return x
    elif y % x == 0:
        return y
    else:
        return (x * y) // gcd(x, y)

# const
THRESHOLED = 10**9+7

# input
N = int(input())
nums = list(map(int, input().split()))

# calculate lcm_num
lcm_num = reduce(lcm, nums)

# make answer
ans = 0
for n in nums:
    ans += lcm_num//n
    if ans >= THRESHOLED:
        ans = ans%THRESHOLED

print(ans)