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:
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
        s = g

data = [0] * (1 << M)
ans = 2 ** (N - 1)
for i in range(1, 1 << M):
    k = len(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: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N, = map(int, input().split())
G = [set() for _ in range(N+1)]
d = dict()
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)
    d[(a,b)] = i
    d[(b,a)] = i
ps = []
M, = map(int, input().split())
for _ in range(M):
    a, b = map(int, input().split())
    stack = [a]
    path = []
    vs = set([a])
    while stack:
        v = stack.pop()
        if v > 0:
            path.append(v)
            if v == b:
                break
            vs.add(v)
            for u in G[v]:
                if u in vs:
                    continue
                vs.add(u)
                stack += [-v, u]
        else:
            path.pop()
    es = 0
    for i in range(len(path)-1):
        es += 1<<d[(path[i], path[i+1])]
    ps.append(es)

r=0
for i in range(2**M):
    p=m=j=0
    x=0
    while i:
        if i%2:
            x=x|ps[j]
            p+=1
        i >>= 1
        j+=1
    r+=(-1 if p%2 else 1)*(1<<(N-1-bin(x).count("1")))
print(r)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-popcount(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = 0
        v = g
        while v != s:
            v, i = par[v]
            r |= 1 << i
        return r
    
    M = int(input())
    path = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-bin(s).count('1'))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = 0
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = set()
        v = g
        while v != s:
            v, i = par[v]
            r.add(i)
        return r
    
    M = int(input())
    path = [None] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-len(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = 0
        s = set()
        for i in range(M):
            if p&1:
                s |= path[i]
                is_odd ^= 1
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        E[a].append((b,i))
        E[b].append((a,i))
    
    def dfs(s, g):
        par = [(-1,-1)] * N
        par[s] = (s,-1)
        stack = [s]
        while stack:
            v = stack.pop()
            for to, i in E[v]:
                if par[to][0] >= 0: continue
                par[to] = (v, i)
                if to == g: break
                stack.append(to)
        r = set()
        v = g
        while v != s:
            v, i = par[v]
            r.add(i)
        return r
    
    M = int(input())
    path = [None] * M
    for i in range(M):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        path[i] = dfs(u, v)

    def calc(s): return 1<<(N-1-len(s))

    i_ans = 0
    for p in range(1, 1<<M):
        is_odd = bin(p).count('1') & 1
        s = set()
        for i in range(M):
            if p&1: s |= path[i]
            p >>= 1
        if is_odd: i_ans += calc(s)
        else: i_ans -= calc(s)

    print((1<<(N-1)) - i_ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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)
coeff = -1
for m in range(1, M+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: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
el = []
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  if u > v: u, v = v, u
  el.append((u, v))

vis = []
def dfs(s, t):
  global vis
  vis.append(s)
  if s == t:
    res = list(vis)
    vis.remove(s)
    return res
  res = []
  for x in e[s]:
    if x in vis: continue
    tt = dfs(x, t)
    if len(tt):
      res = tt
      break
  vis.remove(s)
  return res


M = int(input())
table = [[0] * (N - 1) for _ in range(M)]
for i in range(M):
  u, v = map(int, input().split())
  p = dfs(u, v)
  #print(p, i, vis)
  for j in range(len(p) - 1):
    for k in range(N - 1):
      x = p[j]
      y = p[j + 1]
      if x > y: x, y = y, x
      #print(el[k], x, y, i)
      if el[k] == (x, y):
        table[i][k] = 1
        break
revtable = [0] * (N - 1)
for i in range(N - 1):
  for j in range(M):
    if table[j][i]: revtable[i] += pow(2, j)

dp = [0] * pow(2, M)
dp[0] = 1
#print(revtable)
#print(table)
for i in range(N - 1):
  for j in range(pow(2, M) - 1, -1, -1):
    dp[revtable[i] | j] += dp[j]
print(dp[-1])

Submission status: Accepted

Solution code:
# F - Tree and Constraints

# Read input

n = int(input())
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append((b, i))
    adj[b].append((a, i))
m = int(input())
ranges = [tuple(map(int, input().split())) for i in range(m)]

# Subroutines

def findpath(u, v, parent=None):
    """uからvへの経路 (辺の集合)"""
    if u == v:
        return set()
    for x, i in adj[u]:
        if x == parent:
            continue
        p = findpath(x, v, u)
        if p is not None:
            p.add(i)  # id of edge
            return p
    return None

def powerset(seq, bag):
    """[(seqの部分集合s, bag[e] for e in s の和集合)]"""
    if len(seq) <= 1:
        yield ((seq[0],), bag[seq[0]])
        yield ((), set())
    else:
        for s, b in powerset(seq[1:], bag):
            yield ((seq[0],) + s, b | bag[seq[0]])
            yield (s, b)

# Find paths

paths = [findpath(u, v) for u, v in ranges]

# いずれかの区間をすべて白にする塗り方の個数
white = 0
for s, b in powerset(list(range(m)), paths):
    l = len(s)
    if l <= 0:
        continue
    # b中の辺をすべて白にする塗り方の個数
    w = 2 ** (n - 1 - len(b))
    # 包除原理
    sign = -1 if l % 2 == 0 else 1    
    white += sign * w

# どの区間も黒を含む塗り方の個数
coloring = 2 ** (n - 1) - white
print(coloring)

Submission status: Accepted

Solution code:
# F - Tree and Constraints

# Read input

n = int(input())
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
m = int(input())
ranges = []
for i in range(m):
    u, v = map(int, input().split())
    ranges.append((u, v))

# Subroutines

def normalized(u, v):
    return (min(u, v), max(u, v))

def findpath(u, v, visited=None):
    """uからvへの経路 (辺の集合)"""
    if visited is None:
        visited = set()
    if u == v:
        return set()
    if u in visited:
        return None
    visited.add(u)
    for x in adj[u]:
        p = findpath(x, v, visited)
        if p is not None:
            p.add(normalized(u, x))
            return p

def powerset(seq, bag):
    """(seqの部分集合s, bag[e] for e in s の和集合)"""
    if len(seq) <= 1:
        yield ((seq[0],), bag[seq[0]])
        yield ((), set())
    else:
        for s, b in powerset(seq[1:], bag):
            yield ((seq[0],) + s, b | bag[seq[0]])
            yield (s, b)

# Find paths

paths = {}
for u, v in ranges:
    paths[(u, v)] = findpath(u, v)

# いずれかの区間をすべて白にする塗り方の個数
coloring = 0
for s, b in powerset(ranges, paths):
    l = len(s)
    if l <= 0:
        continue
    # b中の辺をすべて白にする塗り方の個数
    c = 2 ** ((n - 1) - len(b))
    # 包除原理
    sign = -1 if l % 2 == 0 else 1    
    coloring += sign * c

# どの区間も黒を含む塗り方の個数
coloring = 2 ** (n - 1) - coloring
print(coloring)

Submission status: Accepted

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

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

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

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

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


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

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

    NOW=[x]

    while NOW:
        n=NOW.pop()

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

    RET=0
    ANS=[y]
    while y!=x:
        RET+=1<<DICT[tuple(sorted([y,USE[y]]))]
        y=USE[y]

    return RET

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

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

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

print(DP[-1])

Submission status: Accepted

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

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

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
    
graph = [[] for _ in range(N + 1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
  
def make_tree(graph, root) -> (list, list):
  INF = 10 ** 15
  dist = [INF] * len(graph)
  parent = [-1] * len(graph)
  stack = [root]
  dist[root] = 0
  parent[root] = root
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if dist[g] > dist[s] + 1:
        dist[g] = dist[s] + 1
        parent[g] = s
        stack.append(g)
  return dist, parent
 
def lca(u, v, dist, parent):
  distu, distv = dist[u], dist[v]
  if distu > distv:
    for _ in range(distu - distv):
      u = parent[u]
  if distv > distu:
    for _ in range(distv - distu):
      v = parent[v]
  while u != v:
    u, v = parent[u], parent[v]
  return u

dist, parent = make_tree(graph, 1)

tree_lca = []
for i in range(M):
    tmp = 0
    u, v = UV[i]
    l = lca(u, v, dist, parent)
    while u != l:
        tmp |= 1 << u
        u = parent[u]
    while v != l:
        tmp |= 1 << v
        v = parent[v]
    tree_lca.append(tmp)

answer = 2 ** (N - 1)
for i in range(1, 2 ** M):
    tmp = 0
    for j in range(M):
        if (i >> j) & 1:
            tmp |= tree_lca[j]
    cnt = popcnt(tmp)

    if popcnt(i) % 2 == 1:
        answer -= 2 ** (N - 1 - cnt) 
    else:
        answer += 2 ** (N - 1 - cnt) 
        
print(answer)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ls = [list(map(lambda x:int(x)-1, input().split())) for i in range(n-1)]
m = int(input())
cond = [list(map(lambda x:int(x)-1, input().split())) for i in range(m)]
ans=0
graph = [[0]*(n) for _ in range(n)]



for i in range(n-1):
    graph[ls[i][0]][ls[i][1]]+=1<<i
    graph[ls[i][1]][ls[i][0]]+=1<<i

eset = []

for cns in cond:
    d=deque()
    d.append([cns[0], 0])
    while d:
        s, es = d.pop()
        for i in range(n):
            if graph[s][i] and not es&graph[s][i]:
                es2 = es|graph[s][i]
                if i == cns[1]:
                    eset.append(es2)
                    break
                d.append([i, es2])

for i in range(1<<m):
    mask=0
    for j in range(m):
        if i&1<<j:
            mask|=eset[j]
    white=bin(mask).count('1')
    if bin(i).count('1')%2:
        ans-=1<<(n-1-white)
    else:
        ans+=1<<(n-1-white)

print(ans)

Submission status: Accepted

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

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


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


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


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline



n = I()
G = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = LI()
    G[u - 1] += [(i, v - 1)]
    G[v - 1] += [(i, u - 1)]


def dfs(root):
    q = [root]
    path_bit = [-1] * n
    path_bit[root] = 0
    while q:
        u = q.pop()
        for i, v in G[u]:
            if path_bit[v] != -1:
                continue
            path_bit[v] = path_bit[u] | 1 << i
            q += [v]
    return path_bit



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


m = I()
cond = LIR(m)
path_bit = dfs(0)
cond_bit = [0] * m
for j, (u, v) in enumerate(cond):
    cond_bit[j] = path_bit[u - 1] ^ path_bit[v - 1]

L = [0] * (2 ** m)
C = [0] * n
for i in range(2 ** m):
    if i != 0:
        L[i] = L[(i ^ (i & -i))] | cond_bit[(i & -i).bit_length() - 1]
# それぞれの条件を満たさないものを全事象から引く。
# 次に、2個同時に条件を満たさないものをたす。という要領。
    cond_cnt = popcnt(i)
# p_cnt が満たさない条件の数。
    if cond_cnt % 2:
        C[n - 1 - popcnt(L[i])] -= 1
    else:
        C[n - 1 - popcnt(L[i])] += 1


ans = 0
for i in range(n):
    ans += 2 ** i * C[i]


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
edge = [0 for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        edge[y] = edge[x] + 2**(y-1)
        seen[y] = 1
        now.append(y)

def count1(x):
  y = bin(x)
  z = 0
  l = len(y)
  for li in range(l):
    if y[li] == '1':
      z += 1
  return z

def count2(x):
  z = 0
  l = len(x)
  for li in range(l):
    if x[li] == '1':
      z += 1
  return z


m = int(input())
restr = []
for _ in range(m):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  restr.append(edge[u]^edge[v])
#print(edge)
#print(restr)

ans = 0
for i in range(2**m):
  b = bin(i)[2:]
  time = '0' * (m-len(b)) + b
  tmp = 0
  for j in range(m):
    if time[j] == '1':
      tmp |= restr[j]
  if count2(time) % 2 == 0:
    ans += 2**(n-1-count1(tmp))
    #print('+',count2(time),time,count1(tmp),ans,bin(tmp))
  else:
    ans -= 2**(n-1-count1(tmp))
    #print('-',count2(time),time,count1(tmp),ans,bin(tmp))
#print(restr)
print(ans)

Submission status: Accepted

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 = [0]*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] |= 1 << i

import itertools

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

Submission status: Accepted

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

dp = [0] * M
def dfs(cur, pre, t, i) :
  if cur == t : return True
  for nex, j in ab[cur] :
    if nex == pre : continue
    if dfs(nex, cur, t, i) :
      dp[i] |= 1<<j
      return True
  return False

for i, (u, v) in enumerate(uv) :
  dfs(u-1, -1, v-1, i)

ret = 1<<(N-1)
for i in range(1, 1<<M) :
  sgn = 1
  s = 0
  for j in range(M) :
    if i & (1<<j) :
      s |= dp[j]
      sgn *= -1
  ret += sgn * (1<<(N-1-bin(s).count('1')))

print(ret)

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ in range(n)]
e = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
    e.append((a - 1, b - 1))
m = int(input())
l = [set() for _ in range(m)]
for i in range(m):
    u, v = map(int, input().split())
    s = [u - 1]
    dist = [-1] * n
    dist[u - 1] = 0
    r = [-1] * n
    while s:
        d = s.pop()
        for node in g[d]:
            if dist[node] == -1:
                s.append(node)
                dist[node] = dist[d] + 1
                r[node] = d
    d = v - 1
    while r[d] != -1:
        a, b = min(d, r[d]), max(d, r[d])
        l[i].add(e.index((a, b)))
        d = r[d]
ans = 0
for i in range(2 ** m):
    cnt = 0
    s = set()
    for j in range(m):
        if (i >> j) & 1:
            cnt += 1
            s |= l[j]
    if cnt % 2:
        ans -= 2 ** (n - len(s) - 1)
    else:
        ans += 2 ** (n - len(s) - 1)
print(ans)

Submission status: Accepted

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

#立っている場所の個数
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

def main():
    n = int(input())
    edge = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    m = int(input())
    dg = 100
    uv = []
    for _ in [0]*m:
        u,v = map(int,input().split())
        uv.append(u*dg-dg+v-1)

    #各点の親を求める
    par = [-2]*n
    root = 0
    par[0] = -1

    tank = [0]
    order = []
    orderIdx = [0]*n
    cnt = 0
    while tank:
        now = tank.pop()
        for nxt in edge[now]:
            if par[nxt] == -2:
                par[nxt] = now
                tank.append(nxt)
        order.append(now)
        orderIdx[now] = cnt
        cnt += 1
    
    res = pow(2,n-1)
    #1ビットだけ立っているもの
    bitOne = set()
    for i in range(m):
        bitOne.add(1<<i)

    #dp
    dp = [0]*(1<<m)
    for i in range(1,1<<m):
        pc = popcnt(i)
        if pc == 1:
            #idx:iで立っているbitの内最後のもののindex
            idx = (-i&i).bit_length()-1
            
            u,v = uv[idx]//dg,uv[idx]%dg

            
            #u,v間の経路の辺を立てたものがdp[i]
            tmp = 0
            while u != v:
                if orderIdx[u] < orderIdx[v]:
                    tmp |= (1<<v)
                    v = par[v]
                else:
                    tmp |= (1<<u)
                    u = par[u]
            dp[i] = tmp
        
        else:
            dp[i] = dp[(-i)&i] | dp[((-i)&i)^i]
    
        res += (-1)**(pc%2)*pow(2,n-1-popcnt(dp[i]))

    print(res)

if __name__ == '__main__':
    main()