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:
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 = []
print(road)
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: Wrong Answer

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 bitcount32(n):
    n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555)
    n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333)
    n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F)
    n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF)
    n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF)
    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 = bitcount32(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 - bitcount32(bit)
    val = 2 ** free_link_cnt
    if cnd_cnt % 2:
        ans -= val
    else:
        ans += val
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
from itertools import combinations
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
M = int(input())
uv = [tuple(map(int, input().split())) for i in range(M)]


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


G = [[-1]*N for i in range(N)]
for i in range(N-1):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a][b] = i
    G[b][a] = i

q = collections.deque()

G2 = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    q.append((i, 0))
    reached = [False]*N
    reached[i] = True
    while(q):
        x, s = q.popleft()
        for y in range(N):
            if G[x][y] == -1 or reached[y]:
                continue
            else:
                G2[i][y] = s | (1 << G[x][y])
                q.append((y, s | 1 << G[x][y]))
                reached[y] = True


ans = 2**(N-1)
ans2 = 0

print(ans-ans2)

Submission status: Wrong Answer

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

    edgess = [set() for _ in range(M)]
    for i, (u, v) in enumerate(uvs):
        path = getPath(u, v)
        for j in range(len(path)-1):
            a, b = path[j], path[j+1]
            if a > b:
                a, b = b, a
            edgess[i].add((a, b))

    nums = [0] * (1<<M)
    for u, v in edges:
        mask = 0
        for k in range(M):
            if (u, v) in edgess[k]:
                mask |= 1<<k
        for S in range(1<<M):
            if S & mask == mask:
                nums[S] += 1

    ans = 0
    for S in range(1<<M):
        num1 = bin(S).count('1')
        if num1 % 2:
            ans += 2**nums[S] - 1
        else:
            ans -= 2**nums[S] - 1

    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def cal(tree, v, bit, pre_node, now_node):
  for node in tree[now_node]:
    new_bit = bit | (1 << node)
    if node == v:
      return new_bit
    if node == pre_node:
      continue
    new_bit = cal(tree, v, new_bit, now_node, node)
    if new_bit:
      return new_bit
  return False

def run():
  N = int(input())
  tree = {}
  for n in range(1, N):
    a, b = map(int, input().split())
    tree.setdefault(a, []).append(b)
    tree.setdefault(b, []).append(a)
  #print(tree)
  M = int(input())
  uv = [0]*M
  for m in range(M):
    u, v = map(int, input().split())
    bit = 1 << u
    uv[m] = cal(tree, v, bit, -1, u)
    #print(bin(uv[m]))
  ans = 2**(N-1)
  for m in range(1, M+1):
    total = 0
    #print(m)
    for units in combinations(uv, m):
      #print(units)
      temp = 0
      white = 0
      for bit in units:
        white += bin(bit).count('1')-1
        dup = temp & bit
        n_dup = bin(dup).count('1')
        if n_dup >= 2:
          white -= n_dup-1
        temp |= bit
      #print(bin(temp))
      #white = bin(temp).count('1')
      black = N-white-1
      #print(black)
      total += 2**black
    if m%2 == 0:
      #print('m'+str(m))
      ans += total
    else:
      ans -= total
  print(ans)

if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

def cal(tree, v, bit, pre_node, now_node):
  for node in tree[now_node]:
    new_bit = bit | (1 << node)
    if node == v:
      return new_bit
    if node == pre_node:
      continue
    new_bit = cal(tree, v, new_bit, now_node, node)
    if new_bit:
      return new_bit
  return False

def run():
  N = int(input())
  tree = {}
  for n in range(1, N):
    a, b = map(int, input().split())
    tree.setdefault(a, []).append(b)
    tree.setdefault(b, []).append(a)
  #print(tree)
  M = int(input())
  uv = [0]*M
  for m in range(M):
    u, v = map(int, input().split())
    bit = 1 << u
    uv[m] = cal(tree, v, bit, -1, u)
    #print(bin(uv[m]))
  ans = 2**(N-1)
  for m in range(1, M+1):
    total = 0
    #print(m)
    for units in combinations(uv, m):
      #print(units)
      temp = 0
      for bit in units:
        temp |= bit
      #print(bin(temp))
      white = bin(temp).count('1')
      black = N-white
      #print(black)
      total += 2**black
    if m%2 == 0:
      #print('m'+str(m))
      ans += total
    else:
      ans -= total
  print(ans)

if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:


#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n = ii()
    e = [[]for i in range(n)]
    for i in range(n-1):
        a,b = mi()
        e[a-1].append([b-1,i])
        e[b-1].append([a-1,i])

    m = ii()
    mlist = []
    for i in range(m):
        u,v = mi()
        mlist.append([u-1,v-1])

    way = [[[]for i in range(n)] for j in range(n)]

    for s in range(n):
        stack = []
        waytmp = [0 for i in range(n-1)]
        stack.append([s,waytmp])
        while stack:
            tmp = stack.pop()
            p = tmp[0]
            for tt in tmp[1]:
                way[s][p].append(tt)
            w = []
            for wtmp in e[p]:
                for ttt in way[s][p]:
                    w.append(ttt)
                if w[wtmp[1]] == 1:
                    continue
                w[wtmp[1]] = 1
                stack.append([wtmp[0],w])

    ans = 0
    for _ in range(1,m+1):
        comall = itertools.combinations(range(m), _)
        for com in comall:
            wt = [0 for sdfhjk in range(n-1)]
            for w in com:
                for i in range(n-1):
                    wt[i] += way[mlist[w][0]][mlist[w][1]][i]
            cnt = 0
#            print("wt is ", wt)
            for i in range(n-1):
                if wt[i] == 0:
                    cnt+=1
            
#            print("cnt is ",cnt)
            if _%2:
                ans+=2**cnt
            else:
                ans-=2**cnt
    #print(way)
    print(2**(n-1)-ans)



    

        



main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(100*u+v)
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    for v in range(N-1):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    M, = map(int, readline().split())
    qs = set()
    ss = set()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        qs.add((u,v))
        ss.add(u)
    dep = dict()
    for i in ss:
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if (i,u) in qs:
                        dep[(i,u)] = con(path+[u])
                    stack += [-v, u]
            else:
                path.pop()
    qs = list(qs)
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = set()
        for j in range(M):
            if i % 2:
                ns = ns | dep[qs[j]]
                t += 1
            i = i>>1
        xx = (1 if (t+M)%2 else -1)*2**(N-1-len(ns))
#        print(i, xx)
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()

Submission status: Wrong Answer

Solution code:
n = int(input())

g = [[] for _ in range(n)]
edge = {}


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

m = int(input())

visited = [False]*n
hist = []


def dfs(v):
    visited[v] = True
    hist.append(v)
    for w in g[v]:
        if not visited[w]:
            dfs(w)
            hist.append(v)

dfs(0)

intv = [[0 for _ in range(n-1)] for __ in range(m)]


for i in range(m):
    u, v = map(int, input().split())
    uind = hist.index(u-1)
    vind = hist.index(v-1)
    uind = min(uind, vind)
    vind = max(uind, vind)
    for j in range(uind, vind):
        intv[i][edge[(hist[j], hist[j+1])]] += 1
        intv[i][edge[(hist[j], hist[j+1])]] %= 2


mm = 1 <<m

ans = 0

for i in range(mm):
    a = [1]*(n-1)
    cnt = 0
    for j in range(m):
        if (i >> j) & 1:
            cnt += 1
            for k in range(n-1):
                if intv[j][k] == 1:
                    a[k] = 0
    ans += ((-1)**(cnt))*2**(sum(a))

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dijkstra(s):
        d = [float("inf")]*n
        p = [s]*n
        d[s] = 0
        q = [(0,s)]
        while q:
            dx,x = heappop(q)
            nd = dx+1
            for y in v[x]:
                if nd < d[y]:
                    d[y] = nd
                    p[y] = x
                    heappush(q,(nd,y))
        path = [[i] for i in range(n)]
        for i in range(1,n):
            pre = path[i][-1]
            while pre != s:
                path[i].append(p[pre])
                pre = path[i][-1]
            path[i] = path[i][::-1]
        return d,path

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [[0]*n for i in range(n)]
    path = [[None]*n for i in range(n)]
    for i in range(n):
        D,p = dijkstra(i)
        d[i] = [j for j in D]
        path[i] = [j for j in p]
    m = I()
    l = LIR(m)
    for i in range(m):
        l[i][0] -= 1
        l[i][1] -= 1
    ans = 0
    fa = 0
    fb = 0
    for b in range(1,1<<m):
        f = bin(b).count("1")
        p = [0]*n
        for j in range(m):
            x,y = l[j]
            if b&(1<<j):
                for k in path[x][y]:
                    p[k] = 1
        s = 0
        for j in p:
            s += j
        f &= 1
        k = 1<<(n-s)
        if f:
            ans += k
        else:
            ans -= k
    print((1<<(n-1))-ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]
m = int(input())
U = [list(map(int,input().split())) for i in range(m)]

for i in range(n-1):
    for j in range(2):
        C[i][j] -= 1
for i in range(m):
    for j in range(2):
        U[i][j] -= 1

B = [[0] * (m) for i in range(n-1)]

M = [[] for i in range(n)]
for i in range(n-1):
    M[C[i][0]].append([C[i][1], 1])  # 無向グラフなら両方追加
    M[C[i][1]].append([C[i][0], 1])  # 無向グラフなら両方追加

E = [[-1] * n for i in range(n)]
for i in range(n-1):
    E[C[i][0]][C[i][1]] = i
    E[C[i][1]][C[i][0]] = i  

F = [[] for i in range(m)]
import heapq

for mm in range(m):
    uu = U[mm][0]
    vv = U[mm][1]

    D = [float("inf")] * n  # 頂点0からの距離
    P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
    D[uu] = 0
    V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
    Q = []  # 優先度付きキュー
    for v in range(n):
        heapq.heappush(Q, [D[v], v])

    le = len(Q)
    while le > 0:
        q = heapq.heappop(Q)
        u = q[1]
        du = q[0]
        if V[u] == 0:
            V[u] = 1
            le -= 1
            for i in range(len(M[u])):
                v = M[u][i][0]
                luv = M[u][i][1]
                if V[v] == 0:
                    alt = du + luv
                    if D[v] > alt:
                        D[v] = alt
                        P[v] = u
                        heapq.heappush(Q, [alt, v])

    # print(P)
    tt = vv
    while tt != uu:
        ss = P[tt]
        F[mm].append(E[ss][tt])
        print(ss,tt)
        tt = ss

print("F",F)

for i in range(m):
    for j in F[i]:
        B[j][i] = 1



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

# B.sort(key=lambda x:sum(x))

BB = [[] for i in range(m+1)]
for i in range(len(B)):
    BB[sum(B[i])].append(B[i][:])
# print(BB)
CC = []
for i in range(len(BB)):
    for j in range(len(BB[i])):
        CC.append(BB[i][j])
B=CC
import itertools
# print("B",B)
G = [0] * (2**m)
G[0] = 1
for i in range(n-1):
    ii = 0
    K = []
    for j in range(m):
        if B[i][j] == 1:
            K.append(j)
        ii += B[i][j] * M2[m-1-j]
    # print(ii)

    GG = G[:]
    for jj in range(2**m):
        GG[jj | ii] += G[jj]
    G = GG[:]
    # print("K",K)
    # for jj in range(len(K), -1, -1):
    #     TT = list(itertools.combinations(K, jj))
    #     print(jj,TT)
    #     for j in range(len(TT)):
    #         tt = 0
    #         for bb in range(len(TT[j])):
    #             tt += M2[m-1-TT[j][bb]]
    #         print("tt",tt)
    #         G[ii] += G[tt]
    #         G[tt] += G[tt]
    # print("G",G)

print(G[-1])




# M = [[] for i in range(n)]
# for i in range(n-1):
#     M[A[i][0]].append([A[i][1], i])
#     M[A[i][1]].append([A[i][0], i])

# for i in range(m):
#     ok = 0
#     u = U[i][0]
#     v = U[i][1]
#     Q = [u]
#     E = []
#     V = [0] * n
#     V[u] = 1
#     while len(Q) > 0:
#         qq = Q.pop()
#         t = 0
#         for j in M[qq]:
#             jj = j[0]
#             if V[jj] == 0:
#                 t = 1
#                 V[jj] = 1
#                 Q.append(jj)
#                 E.append(j[1])
#                 if jj == v:
#                     ok = 1
#                     break
#         if ok == 1:
#             break
#         if t == 0:
#             ee = E.pop()

Submission status: Wrong Answer

Solution code:
n=int(input())
edges=[list(map(int,input().split()))for _ in range(n-1)]
m=int(input())
mm=[list(map(int,input().split()))for _ in range(m)]
dp=[(1<<m)*[0]for _ in range(n)]
for i in range(n):dp[i][0]=1
edge=[[]for _ in range(n)]
for a,b in edges:
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
tree=[-1]*n
Q=[0]
visited={0}
cnt=0
v=[[]for _ in range(n)]
vv=[0]*n
while Q:
  P=[]
  for i in Q:
    f=True
    for j in edge[i]:
      if j in visited:continue
      f=False
      tree[j]=i
      visited.add(j)
      P.append(j)
    v[cnt].append(i)
    vv[i]=cnt
  Q=P
  cnt+=1
v=v[:cnt]
ms=[set()for _ in range(m)]
for i in range(m):
  ma,mb=mm[i]
  ma-=1
  mb-=1
  ms[i]={ma,mb}
  if vv[ma]<vv[mb]:ma,mb=mb,ma
  if vv[ma]>vv[mb]:
    for j in range(vv[ma]-vv[mb]):
      ma=tree[ma]
      ms[i].add(ma)
  while ma!=mb:
    ma=tree[ma]
    mb=tree[mb]
    ms[i]|={ma,mb}
for c in range(len(v)-1,0,-1):
  for i in v[c]:
    if c==len(v)-1:dp[i][0]=1
    jj=0
    for j in range(m):
      jj*=2
      if i in ms[j]:jj+=1
    for j in range(1<<m):
      dp[tree[i]][j|jj]+=dp[i][j]
ans=0
jj=0
for j in range(m):
  jj*=2
  if 0 in ms[j]:jj+=1
for j in range(1<<m):
  if j|jj==(1<<m):ans+=dp[0][j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(1000*u+v)
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    for v in range(N-1):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    M, = map(int, readline().split())
    qs = set()
    ss = set()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        qs.add((u,v))
        ss.add(u)
    dep = dict()
    for i in ss:
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if (i,u) in qs:
                        dep[(i,u)] = con(path[:]+[u])
                    stack += [-v, u]
            else:
                path.pop()
    qs = list(qs)
    r = 0
    for i in range(2**M):
        t = 0
        ns = set()
        for j in range(M):
            if i % 2:
                ns = ns | dep[qs[j]]
                t += 1
            i = i>>1
        xx = (1 if (t+M)%2 else -1)*2**(N-1-len(ns))
#        print(i, xx)
        r += xx
    print(r)
if __name__ == '__main__':
    process()

Submission status: Wrong Answer

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

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

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

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


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

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(100*u+v)
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    for v in range(N-1):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    M, = map(int, readline().split())
    qs = set()
    ss = set()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        qs.add((u,v))
        ss.add(u)
    dep = dict()
    for i in ss:
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if (i,u) in qs:
                        dep[(i,u)] = con(path[:]+[u])
                    stack += [-v, u]
            else:
                path.pop()
    qs = list(qs)
    r = 0
    for i in range(2**M):
        t = 0
#        ns = set(range(1,N+1))
        ns = set()
        for j in range(M):
            if i % 2:
                ns = ns | dep[qs[j]]
                t += 1
            i = i>>1
        xx = (1 if (t+M)%2 else -1)*2**(N-1-len(ns))
#        print(i, xx)
        r += xx
    print(r)
if __name__ == '__main__':
    process()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]


def bfs(s,n,g,t): # 木構造の距離の算出 start, number, graph
    went = [False]*n
    dis = [0]*n
    que = deque([])
    que.append(s)
    went[s] = True
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            que.append(g[go][i])
    root = []
    root.append(t)
    x = dis[t]
    que1 = deque([])
    que1.append(t)
    while que1:
        go = que1.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] == x-1:
                que1.append(g[go][i])
                root.append(g[go][i])
                x -=1
                break
        if x == 0:
            break
    return root


def main():
    n = inp()
    g=[[] for _ in range(n)]
    # ab = []
    path = defaultdict(int)
    for i in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        path[str(a)+' '+str(b)] = i+1
        path[str(b)+' '+str(a)] = i+1
        # ab.append((a,b))
        g[b].append(a)
        g[a].append(b)
    print(path)
    m = inp()
    ans = 0
    pre_root = [[] for _ in range(m)]
    for j in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        root1 = bfs(u,n,g,v)
        for i in range(len(root1)-1):
            a,b = root1[i],root1[i+1]
            x = path[str(a)+' '+str(b)]
            pre_root[j].append(x)
    for k in range(pow(2,n-1)):
        color = []
        for _ in range(n-1):
            color.append(k%2)
            k //= 2
        flag = 1
        for i in range(m):
            flag1 = 0
            for j in range(len(pre_root[i])):
                go = pre_root[i][j]-1
                if color[go] == 1:
                    flag1 = 1
                    break
            if not flag1:
                flag = 0
                break
        if flag:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll):
    rs = []
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        rs.append(100*u+v)
    return set(rs)

def process():
    G = [[] for _ in range(N+1)]
    for v in range(N-1):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    M, = map(int, readline().split())
    qs = set()
    for _ in range(M):
        u, v = map(int, readline().split())
        qs.add((u,v))
    dep = dict()
    for i in range(1, N+1):
        path = []
        stack = [i]
        vs = set([i])
        while stack:
            v = stack.pop()
            if v > 0:
                vs.add(v)
#                parent = path[-1]
                path.append(v)
                for u in G[v]:
                    if u in vs:
                        continue
                    if (i,u) in qs:
                        dep[(i,u)] = con(path[:]+[u])
                    stack += [-v, u]
            else:
                path.pop()
    qs = list(qs)
    r = 0
    for i in range(2**M):
        t = 0
#        ns = set(range(1,N+1))
        ns = set()
        for j in range(M):
            if i % 2:
                ns = ns | dep[qs[j]]
                t += 1
            i = i>>1
        xx = (1 if (t+M)%2 else -1)*2**(N-1-len(ns))
#        print(i, xx)
        r += xx
    print(r)
if __name__ == '__main__':
    process()