abc 152 F - Tree and Constraints (python)

一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。
m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表記として保管した。複数の path を選ぶ時の辺集合を path1 | path2 | ... として表現することが出来る。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque,defaultdict

def all_bit_count(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
  
n = int(readline())
d = defaultdict(int)
cnt = 1

g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

m = int(readline())
c = []
for i in range(m):
  u, v = map(int,readline().split())
  u -= 1
  v -= 1  
  que = deque()
  que.append((u,0))
  chk = [False]*n
  chk[u] = True
  while que:
      now,L = que.popleft()
      if now == v:
        c.append(L)
        break
      for i in g[now]:
          if not chk[i]:
            chk[i] = True
            mi = min(now,i)
            ma = max(now,i)
            mm = mi*100+ma
            if d[mm] == 0:
              d[mm] = cnt
              cnt += 1
            que.append((i,L|(1<<d[mm])))
                     
import itertools
ans = 1<<(n-1)
for i in range(1,m+1):
  for j in itertools.combinations(c,i):
    K = 0
    for k in j:
      K |= k
    l = all_bit_count(K)
    ans += pow(-1,i)*pow(2,n-1-l)
    
print(ans)