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: Accepted

Solution code:
import sys
readline = sys.stdin.readline
popcntsum = ((1<<64) - 1)
Fa = [0] + [popcntsum//((1<<(1<<(i-1)))+1) for i in range(1,7)]
Fb = [0] + [Fa[i]<<(1<<(i-1)) for i in range(1,7)]
fila1 = Fa[1]
filb1 = Fb[1]
fila2 = Fa[2]
filb2 = Fb[2]
fila3 = Fa[3]
filb3 = Fb[3]
fila4 = Fa[4]
filb4 = Fb[4]
fila5 = Fa[5]
filb5 = Fb[5]
fila6 = Fa[6]
filb6 = Fb[6]
def popcount(x):
    x = (x&fila1) + ((x&filb1)>>1)
    x = (x&fila2) + ((x&filb2)>>2)
    x = (x&fila3) + ((x&filb3)>>4)
    x = (x&fila4) + ((x&filb4)>>8)
    x = (x&fila5) + ((x&filb5)>>16)
    x = (x&fila6) + ((x&filb6)>>32)
    return x

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    Enum = [None]*N
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf, num in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            Enum[vf] = num
            ast(vf)
    return par, order, Enum

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


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

root = 0
P, L, Enum = parorder(Edge, root)
#C = getcld(P)

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

dp = [0]*(1<<M)
ans = pow(2, N-1)
for S in range(1, 1<<M):
    pc = popcount(S)
    if pc == 1:
        i = (-S&S).bit_length() - 1
        table = [False]*(N-1)
        u, v = Q[i]
        u -= 1
        v -= 1
        while u != root:
            table[Enum[u]] = not table[Enum[u]]
            u = P[u]
        while v != root:
            table[Enum[v]] = not table[Enum[v]]
            v = P[v]
        res = 0
        for t in table:
            res <<= 1
            res |= t
        dp[S] = res
    else:
        dp[S] = dp[S^(-S&S)]|dp[-S&S]
    
    ans += (-1)**(pc%2)*pow(2, N-1-popcount(dp[S]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
DE = [0] * N
Q = [0]
while Q:
    i = Q.pop()
    for a in X[i][::-1]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] + 1
            X[a].remove(i)
            Q.append(a)

def lp(u, v):
    t = 0
    while u != v:
        if DE[u] > DE[v]:
            t += 1 << u-1
            u = P[u]
        elif DE[u] < DE[v]:
            t += 1 << v-1
            v = P[v]
        else:
            t += 1 << u-1
            t += 1 << v-1
            u = P[u]
            v = P[v]
    
    return t

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

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

D = {1<<i: i for i in range(50)}
Z = [0] * (1<<M)
ans = 0
CC = [0] * N
for m in range(1<<M):
    a = m & (-m)
    if a == m:
        if a == 0:
            Z[m] = 0
        else:
            Z[m] = Y[D[a]]
    else:
        Z[m] = Z[m^a] | Y[D[a]]
    
    CC[N - 1 - popcnt(Z[m])] += (1 if popcnt(m) & 1 == 0 else -1)

print(sum([2 ** i * CC[i] for i in range(N)]))

Submission status: Accepted

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

N = int(input())
graph = [[] for _ in range(N)]
Edges = [[None]*N for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    Edges[a-1][b-1] = i
    Edges[b-1][a-1] = i

def dfs(p, L, checked, goal):
    if p == goal:
        return L
    checked[p] = True
    ok = False
    for np in graph[p]:
        if not checked[np]:
            L.append(np)
            retL = dfs(np, L, checked, goal)
            if retL:
                ok = True
                break
            L.pop()
    if ok:
        return retL
    else:
        return []


M = int(input())
Compression = []
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    path = dfs(a, [], [False]*N, b)
    bit = 0
    pre = a
    for p in path:
        bit += 1<<Edges[pre][p]
        pre = p
    Compression.append(bit)

ans = 0
for bitmask in range(1,1<<M):
    whitebit = 0
    for i in range(M):
        if (1<<i)&bitmask:
            whitebit |= Compression[i]
    
    p = 1
    for n in range(M):
        if bitmask&(1<<n):
            p ^= 1
    E = 1
    for m in range(N-1):
        if whitebit&(1<<m) == 0:
            E *= 2
    
    ans += E*(-1)**p

print(2**(N-1)-ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline
N, = map(int, readline().split())
def con(ll,E):
    r = 0
    for u, v in zip(ll,ll[1:]):
        u, v = sorted([u,v])
        r += 1<<E[(u,v)]
    return r

def process():
    G = [[] for _ in range(N+1)]
    E = dict()
    for i in range(N-1):
        a, b = sorted(map(int, readline().split()))
        G[a].append(b)
        G[b].append(a)
        E[(a,b)] = i

    M, = map(int, readline().split())
    qes = dict()
    for _ in range(M):
        u, v = sorted(map(int, readline().split()))
        if u not in qes:
            qes[u] = list()
        qes[u].append(v)
    dep = []
    for i in qes:
        ms = qes[i]
        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 u in ms:
                        dep.append(con(path+[u],E))
                    stack += [-v, u]
            else:
                path.pop()
    r = 0
    for i in range(1,2**M):
        t = 0
        ns = 0
#        lns = 
        for j in range(M):
            if i % 2:
                ns = ns | dep[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*2**(N-1-bin(ns).count("1"))
        r += xx
    print(2**(N-1)-r)
if __name__ == '__main__':
    process()

Submission status: Accepted

Solution code:
#包除原理
#辺の保持をbit演算での保持へ変換するのが辛い
n = int(input())

TE = [[] for _ in range(n)]
TE2 = []
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai -= 1
    bi -= 1
    TE[ai].append(bi)
    TE[bi].append(ai)
    TE2.append((ai,bi))
m  = int(input())
D =[]
for i in range(m):
    ai,bi = map(int ,input().split( ))
    ai -= 1
    bi-=1
    D.append((ai,bi))

bit = 1<<m


P =[0]*n
C = [[] for _ in range(n)]
from collections import deque
Q = deque()
Q.append(0)
V = [0]*n
V[0] = 1

while Q:
    v = Q.popleft()
    for u in TE[v]:
        if not V[u]:
            V[u] = 1
            Q.append(u)
            P[u] = v
            C[v].append(u)
def path(u,v):
    u_p = set()
    tmp1 = u
    while tmp1:
        u_p.add(tmp1)
        tmp1 = P[tmp1]
    u_p.add(tmp1)
    tmp2 = v

    while tmp2 not in u_p:
        tmp2 = P[tmp2]
    pth = 0##
    tmp3 = u
    tmp4 = v
    while tmp3!=tmp2:
        for t in range(n-1):
            if TE2[t] == (tmp3,P[tmp3]) or TE2[t]==(P[tmp3],tmp3):
                pth |= (1<<t)
        tmp3 = P[tmp3]

    while tmp4!= tmp2:
        for t in range(n-1):
            if TE2[t] == (tmp4,P[tmp4]) or TE2[t]==(P[tmp4],tmp4):
                pth |= (1<<t)
        tmp4 = P[tmp4]
    return pth

D2 = [path(D[i][0],D[i][1]) for i in range(m)]
#print(D2)
ans = 2**(n-1)
for i in range(1,bit):
    cnt = 0
    paths = 0
    for j in range(m):
        if (i>>j)&1:
            paths |= D2[j]
            cnt += 1
    cnt2 = 0
    for j in range(n-1):
        cnt2 += (paths>>j)&1
    ans += (-1)**cnt *2**(n-1-cnt2)
print(ans)

Submission status: Accepted

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)]
    e = defaultdict(lambda : 0)
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        e[(a,b)] = i
        e[(b,a)] = i
    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
    B = [0]*m
    for j in range(m):
        x,y = l[j]
        for k in range(len(path[x][y])-1):
            a,b = path[x][y][k],path[x][y][k+1]
            B[j] |= 1<<e[(a,b)]
    for b in range(1,1<<m):
        f = bin(b).count("1")
        p = 0
        for j in range(m):
            if b&(1<<j):
                p |= B[j]
        s = bin(p).count("1")
        f &= 1
        k = 1<<(n-s-1)
        if f:
            ans += k
        else:
            ans -= k
    print((1<<(n-1))-ans)
    return

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


N = int(input())
g = Graph()
d = {}
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    d[(min(a,b),max(a,b))] = i
    g.add_edge(a,b)
    g.add_edge(b,a)

M = int(input())
l = [0]*M
for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    dij = Dijkstra(g,u)
    path = dij.shortest_path(v)
    for j in range(len(path)-1):
        a,b = path[j],path[j+1]
        l[i] += 2**d[(min(a,b),max(a,b))]

c = [0]*(M+1)
p2 = [2**i for i in range(50)]
for n in range(2**M):
    cnt = 0
    x = 0
    for i in range(M):
        if n&p2[i]==p2[i]:
            cnt += 1
            x |= l[i]
    y = 0
    for i in range(N-1):
        if x&p2[i]==p2[i]:
            y += 1
    c[cnt] += p2[N-1-y]

ans = 0
for i in range(M+1):
    if i%2==0:
        ans += c[i]
    else:
        ans -= c[i]

print(ans)

Submission status: Accepted

Solution code:
'''
包除原理
すべての条件を満たしている
2^{N-1}から「どれかの条件を満たしていない」を引けば良い
i番目の条件を満たしていない確率はかんたんに計算できる
Sに属していいないやつが全て条件を満たしていない確率については
Sに対応する辺が全て白となる確率を考えれば良い
'''
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
    edges[(min(a[i],b[i]),max(a[i],b[i]))]=i
M=int(input())
u=[0 for i in range(M)]
v=[0 for i in range(M)]
for i in range(M):
    u[i],v[i]=map(int,input().split())
    u[i]-=1;v[i]-=1
root=[0 for i in range(M)]
for i in range(M):
    q=deque([u[i]])
    parents=[-1 for i in range(N)]
    reached=[0 for i in range(N)]
    while(len(q)>0):
        r=q.popleft()
        reached[r]=1
        for p in G[r]:
            if reached[p]==1:
                continue
            parents[p]=r
            q.append(p)
    x=v[i]
    while(1):
        if parents[x]==-1:
            break
        s=min(x,parents[x])
        t=max(x,parents[x])
        root[i]+=2**edges[(s,t)]
        x=parents[x]
ans=0
def cnt(x):
    ans=0
    for i in range(M):
        if x|(2**i)==x:
            ans+=1
    return ans
q=deque([])
q.append(0)
S=[0 for i in range(2**M)]
reached=[0 for i in range(2**M)]
while(len(q)>0):
    i=q.popleft()
    for j in range(M):
        if i&(2**j)==0:
            S[i|(2**j)]=S[i]|root[j]
            if reached[i|(2**j)]==0:
                q.append(i|(2**j))
                reached[i|(2**j)]=1
    ans+=(-1)**(cnt(i))*2**(N-bin(S[i]).count("1")-1)
print(ans)

Submission status: Accepted

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

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def dfs(s, x, y, r):
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

D = [[-1] * N for _ in range(N)]
for i in range(N - 1):
  a, b = ab[i][0] - 1, ab[i][1] - 1
  a, b = min(a, b), max(a, b)
  D[a][b] = i

NL = [[] for _ in range(M)]
for i in range(M):
  x, y, r = uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1
  L = T.dfs(x, y, r)
  n = L[0]
  t = 0
  for j in range(1, len(L)):
    m = L[j]
    x, y = min(n, m), max(n, m)
    t = t | (1 << D[x][y])
    n = m
  NL[i] = t
  

ans = 1 << (N - 1)
c = 0
for i in range(1, 1 << M):
  t = i
  f = 0
  k = 0
  for j in range(M):
    if t & 1:
      f += 1
      k = k | NL[j]
    t >>= 1
  cnt = bin(k).count("1")
  if f % 2 == 1:
    c += pow(2, (N - 1 - cnt))
  else:
    c -= pow(2, (N - 1 - cnt))
print(ans - c)

Submission status: Accepted

Solution code:
from itertools import combinations

N = int(input())

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

parent = [None]*N
visited = [False]*N
visited[0] = True
def rec(u):
    for v in adj[u]:
        if not visited[v]:
            parent[v] = u
            visited[v] = True
            rec(v)
rec(0)
del adj

M = int(input())


# edge_id to crucial query_id
tasks = []

for q in range(M):
    u,v = map(int,input().split())
    u,v = u-1,v-1
    u2r = []
    v2r = []
    while u is not None:
        u2r.append(u)
        u = parent[u]
    while v is not None:
        v2r.append(v)
        v = parent[v]
    
    for i,(a,b) in enumerate(zip(reversed(u2r), reversed(v2r))):
        if a != b:
            break
    else:
        i += 1
    # path = u2r[:-i] + [u2r[-i]] + list(reversed(v2r[:-i]))
    tasks.append(u2r[:-i]+v2r[:-i])

cnt = 0
sign = 1

for n in range(1,M+1):
    sub = 0
    for p in combinations(range(M),n):
        sub += 2**(N-1-len(set().union(*(tasks[i] for i in p))))
    cnt += sign*sub
    sign *= -1
print(2**(N-1)-cnt)

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations
    n = int(input())
    ab = [tuple(sorted(list(map(int, input().split())))) for _ in [0]*(n-1)]
    m = int(input())
    uv = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    d = dict()
    for i, (a, b) in enumerate(ab):
        d[(a-1, b-1)] = i

    def tree_path(root, goal):
        d = [-1]*n  # 根からの距離
        d[root] = 0
        q = [root]
        cnt = 0
        while q:  # BFS
            cnt += 1
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] == -1:
                        d[j] = cnt
                        qq.append(j)
            q = qq
        now = goal
        path = [goal]
        while True:
            dist = d[now]
            for i in g[now]:
                if d[i] < dist:
                    now = i
                    path.append(i)
                    break
            if dist == 1:
                break
        return path

    seiyaku = [set() for _ in [0]*m]

    for i, (u, v) in enumerate(uv):
        path = tree_path(u-1, v-1)
        for j in range(len(path)-1):
            x, y = min(path[j], path[j+1]), max(path[j], path[j+1])
            seiyaku[i].add(d[(x, y)])

    cnt = 2**(n-1)

    for i in range(1, m+1):
        flag = 1
        if i % 2 == 1:
            flag = -1
        cc = combinations(list(range(m)), i)
        for c in cc:
            s = set()
            for j in c:
                s |= seiyaku[j]
            cnt += (2**(n-1-len(s)))*flag
    print(cnt)


main()

Submission status: Accepted

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: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict, deque
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 2 ** 31 - 1
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) // 2
                self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret = min(ret, self.seg_min[last])
                first = first // 2
                last = last // 2 - 1
            return ret

    def EulerTour(adj, root):
        st = [root]
        ret = []
        seen = [0] * len(adj)
        par = [0] * len(adj)
        depth = [0] * len(adj)
        while st:
            v = st.pop()
            if seen[v]:
                ret.append(v)
                continue
            ret.append(v)
            seen[v] = 1
            if par[v] != 0:
                st.append(par[v])
            for u in adj[v]:
                if seen[u] == 0:
                    st.append(u)
                    par[u] = v
                    depth[u] = depth[v] + 1

        return ret, depth, par

    def f(a, b):
        return a*100+b

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

    et, depth, par = EulerTour(adj, 1)
    segtree = SegTree(len(et) + 1)
    left = [-1] * (N + 1)
    right = [-1] * (N + 1)
    for i, v in enumerate(et):
        segtree.update(i + 1, depth[v])
        if left[v] < 0:
            left[v] = i
        right[v] = i

    M = int(input())
    edge2cond = defaultdict(int)
    for j in range(M):
        a, b = map(int, input().split())
        lca_depth = segtree.query(min(left[a], left[b]) + 1, max(right[a], right[b]) + 1)
        prev = a
        for i in range(depth[a] - lca_depth):
            parent = par[prev]
            edge2cond[parent*100+prev] += 2**j
            prev = parent
        prev = b
        for i in range(depth[b] - lca_depth):
            parent = par[prev]
            edge2cond[parent*100+prev] += 2**j
            prev = parent

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()
    dp = [[0] * (2**M) for _ in range(N)]
    dp[0][0] = 1
    for i, v in enumerate(seq):
        if v == 1:
            continue
        for mask in range(2**M):
            u = par[v]
            mask_new = edge2cond[u*100+v]

            dp[i+1][mask] += dp[i][mask]
            dp[i+1][mask | mask_new] += dp[i][mask]
    print(dp[-1][-1])
    #print(dp)
    #print(edge2cond)


if __name__ == '__main__':
    main()

Submission status: Accepted

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))
        path.add(u*N+_u)
        u = _u
    while v!=w:
        _v = parent[v]
        #path.add((v, _v))
        path.add(v*N+_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-len(path))
    
print(pow(2, N-1) - ans)

Submission status: Accepted

Solution code:
N = int(input())
from collections import defaultdict
G = defaultdict(list)
EdaNum = {}
Ki = [[float('inf')]*(N+1) for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(min(a,b),max(a,b))] = i
    Ki[a][b] = 1
    Ki[b][a] = 1

Next = [[-1]*(N+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        Next[i][j] = j

        
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if Ki[i][k] + Ki[k][j] < Ki[i][j]:
                Ki[i][j] = Ki[i][k] + Ki[k][j]
                Next[i][j] = Next[i][k]

M = int(input())
MM = [set() for i in range(M)]
#print(EdaNum)
#print(Next)
for i in range(M):
    u,v = map(int,input().split())
    now = u
    while now != v:
        nex = Next[now][v]
        MM[i].add(EdaNum[(min(now,nex),max(now,nex))])
        now = nex
        
#print(MM)
import itertools
zero1 = [0,1]
ans = 0

for i in itertools.product(zero1,repeat = M):
    #print(ans)
    count = 0
    root = set()
    for j in range(M):
        if i[j] == 0:
            count += 1
        else:
            root |= MM[j]
    #print(i,len(root),count)
    if (M-count)%2 ==0:
        ans += pow(2,N-1-len(root))
    else:
        ans -= pow(2,N-1-len(root))
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
inf = 10**18
G = [[inf]*N for _ in range(N)]
edges = [[-1]*N for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1][b-1] = i
    edges[b-1][a-1] = i
use = [-1]*N
que = [0]
use[0] = 0
while que:
    v = que.pop()
    u = use[v]
    for nv in range(N):
        if edges[v][nv] == -1 or use[nv] != -1:
            continue
        i = edges[v][nv]
        use[nv]=u^(1<<i)
        que.append(nv)
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]
used = [0]*(1<<M)
cnt = [0]*(1<<M)
ans = 0
for s in range(1, 1<<M):
    for i in range(M):
        if (s>>i)&1:
            u, v = uv[i]
            u, v = u-1, v-1
            p = s^(1<<i)
            used[s] = used[p]|(use[u]^use[v])
            cnt[s] = cnt[p]^1
            break
    res = 0
    for i in range(N-1):
        if used[s]&(1<<i):
            res+=1
    ans+=(-1)**cnt[s]*pow(2, N-1-res)
print(pow(2, N-1)+ans)