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: Runtime Error

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 >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

def swap(x,y):
  return y,x

def count_ones_by_bin(n):
  bin_n = bin(n)[2:]
  count = 0
  for i in bin_n:
    count += int(i)
  return count

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

N = int(input())
LOG_N = math.floor(math.log(N)/math.log(2))

#{node:[depth,ancestor]}
dic = {}
for i in range(N-1):
  a,b = list(map(int,input().split()))
  if i == 0:
    dic[a] = [0,-1]
  if a in dic:
    dic[b] = [dic[a][0]+1,a]
  else:
    dic[a] = [dic[b][0]+1,b]

#table[k][i]: i's 2^k-th ancestor
table = [[0 for i in range(N+1)] for j in range(LOG_N+1)] 

for i in range(1,N+1):
  table[0][i] = dic[i][1]

for k in range(LOG_N):
  for i in range(1,N+1):
    if (table[k][i] == -1):
      table[k+1][i] = -1
    else:
      table[k+1][i] = table[k][table[k][i]]

def lca(u,v):
  if dic[u][0] > dic[v][0]:
    u,v = swap(u,v)
  for i in range(LOG_N+1)[::-1]:
    if ((dic[v][0] - dic[u][0]) >> i) & 1:
      v = table[i][v]
  if u == v:
    return u
  for i in range(LOG_N+1)[::-1]:
    if table[i][u] != table[i][v]:
      u = table[i][u]
      v = table[i][v]
  return table[0][u]

#path to root
@lru_cache(maxsize=None)
def path_to_root(i):
  if i == 1:
    return 0
  return path_to_root(table[0][i])+2**i

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


accum = 2**(N-1)
for i in range(1,2**M):
  choice = []
  for j in range(M):
    if (i >> j) & 1:
      choice.append(l[j])
  cover = 0
  for item in choice:
    u = item[0]
    v = item[1]
    u_ = path_to_root(u) - path_to_root(lca(u,v))
    v_ = path_to_root(v) - path_to_root(lca(u,v))
    cover = cover | u_ | v_
  
  conditions = len(choice)
  paths = count_ones_by_bin(cover)
  
  accum += 2 ** (N-1-paths) * (((M-conditions)%2)*2-1)


    
print(accum)

Submission status: Runtime Error

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

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

def swap(x,y):
  return y,x

def count_ones_by_bin(n):
  bin_n = bin(n)[2:]
  count = 0
  for i in bin_n:
    count += int(i)
  return count

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

N = int(input())
LOG_N = math.floor(math.log(N)/math.log(2))

#{node:[depth,ancestor]}
dic = {}
for i in range(N-1):
  a,b = list(map(int,input().split()))
  if i == 0:
    dic[a] = [0,-1]
  if a in dic:
    dic[b] = [dic[a][0]+1,a]
  else:
    dic[a] = [dic[b][0]+1,b]

#table[k][i]: i's 2^k-th ancestor
table = [[0 for i in range(N+1)] for j in range(LOG_N+1)] 

for i in range(1,N+1):
  table[0][i] = dic[i][1]

for k in range(LOG_N):
  for i in range(1,N+1):
    if (table[k][i] == -1):
      table[k+1][i] = -1
    else:
      table[k+1][i] = table[k][table[k][i]]

def lca(u,v):
  if dic[u][0] > dic[v][0]:
    u,v = swap(u,v)
  for i in range(LOG_N+1)[::-1]:
    if ((dic[v][0] - dic[u][0]) >> i) & 1:
      v = table[i][v]
  if u == v:
    return u
  for i in range(LOG_N)[::-1]:
    if table[i][u] != table[i][v]:
      u = table[i][u]
      v = table[i][v]
  return table[0][u]

#path to root
@lru_cache(maxsize=None)
def path_to_root(i):
  if i == 1:
    return 0
  return path_to_root(table[0][i])+2**i

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


accum = 2**(N-1)
for i in range(1,2**M):
  choice = []
  for j in range(M):
    if (i >> j) & 1:
      choice.append(l[j])
  cover = 0
  for item in choice:
    u = item[0]
    v = item[1]
    u_ = path_to_root(u) - path_to_root(lca(u,v))
    v_ = path_to_root(v) - path_to_root(lca(u,v))
    cover = cover | u_ | v_
  
  conditions = len(choice)
  paths = count_ones_by_bin(cover)
  
  accum += 2 ** (N-1-paths) * (((M-conditions)%2)*2-1)


    
print(accum)

Submission status: Runtime Error

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: Runtime Error

Solution code:
import copy
#競プロでよくあるグラフの標準入力から隣接リストを得る
N=int(input())#N=頂点数 
q=[[0 for z in range(N+1)] for y in range(N+1)]
p = []
for i in range(N-1):
  x=list(map(int,input().split()))
  x.sort()
  p.append(x)
  q[x[0]][x[1]]=i+1
#隣接リスト
l = [[] for i in range(N+1)]
for pi in p:  #0-originedに注意
  l[pi[0]].append(pi[1])
  l[pi[1]].append(pi[0])
for i in range(1,N+1):
  l[i].sort()
#print(l) #l[i]=iと隣接している頂点の集合
M=int(input())

def route(x,y,l,p,q):
  frag=0
  for i in l[x]:
    if i==y:
      z=sorted([x,y])
      t=q[z[0]][z[1]]
      p.append(t)
      frag==1
      return p
  if frag==0:
    for j in l[x]:
      l[j].remove(x)
      if l[j] != []:
        z=sorted([x,j])
        t=q[z[0]][z[1]]
        p.append(t)
        return route(j,y,l,p,q)
      
L=[]
for i in range(M):
  l1 = copy.deepcopy(l)
  a,b=map(int,input().split())
  L.append(route(a,b,l1,[],q))

def uni(L):
  a=L[0]
  for i in range(1,len(L)):
    a=list(set(L[i]) & set(a))
  return a

A=[w for w in range(M)]
c=0
for i in range(1 << len(A)):
    output = []
    for j in range(len(A)):
        if ((i >> j) & 1) == 1:
            output.append(A[j])
    if len(output)>0:
      a=L[output[0]]
      for k in output:
        a=list(set(L[k]) | set(a))
      s=len(a)
      c=c+(2**(N-1-s))*((-1)**(len(output)+1))
ans=2**(N-1)-c
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
adj = [[] for _ in range(n)] # 辞書の箱を作る
adj_dict = dict()

for i in range(N - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

# 深さ優先探索
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (N - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

void dfs(ll now, ll p, const vector<vector<pll>>& g, vl& path_bit) {
  for (auto&& i : g[now]) {
    if (i.first != p) {
      path_bit[i.first] |= path_bit[now] | (1LL << i.second);
      dfs(i.first, now, g, path_bit);
    }
  }
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);

  ll n, m;
  cin >> n;
  vl a(n-1), b(n-1);
  vector<vector<pll>> g(n);

  rep(i, n-1) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
    g[a[i]].emplace_back(b[i], i);
    g[b[i]].emplace_back(a[i], i);
  }

  cin >> m;
  vl u(m), v(m);
  rep(i, m) {
    cin >> u[i] >> v[i];
    u[i]--;
    v[i]--;
  }

  vl path_bit(n);
  path_bit[0] = 0;
  dfs(0, 0, g, path_bit);
  rep(i, n) {
    //cerr << bitset<10>(path_bit[i]) << endl;
  }

  ll ans = 0;
  rep(bit, 1LL<<m) {
    ll edge_bit = 0;
    rep(i, m) {
      if (bit >> i & 1) {
        edge_bit |= (path_bit[u[i]] xor path_bit[v[i]]);
      }
    }
    ll cnt = __builtin_popcountll(bit);
    ans += (cnt%2 ? -1 : 1) * (1LL << (n-1-__builtin_popcountll(edge_bit)));
    //cerr << ans << endl;
  }
    assert(ans >= 0);
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
class Point:
    def __init__(self, name):
        self.name = name
        self.parent = None
        self.children = []
        self.idx = [name]

    def s_idx(self, idx, root):
        root.append(self.name)
        if self.name == idx:
            return root
        for c in self.children:
            if idx in c.idx:
                return c.s_idx(idx, root)
        return self.parent.s_idx(idx, root)
    def add_idx(self,idx):
        self.idx.append(idx)
        if self.parent:
            self.parent.add_idx(idx)
n = int(input())
path = {}
tree = {}
role = []
for p in range(n-1):
    buf = [int(x) for x in input().split()]
    buf_p = (str(min(*buf)), str(max(*buf)))
    path[tuple(buf_p)] = False
    if buf_p[0] not in tree.keys():
        tree[buf_p[0]] = Point(buf_p[0])
    if buf_p[1] not in tree.keys():
        tree[buf_p[1]] = Point(buf_p[1])
    tree[buf_p[0]].children.append(tree[buf_p[1]])
    tree[buf_p[1]].parent = tree[buf_p[0]]
    tree[buf_p[0]].add_idx(tree[buf_p[1]].name)

m = int(input())
for p in range(m):
    buf = input().split()
    s = buf[0]
    buf_path = []
    buf_root = tree[buf[0]].s_idx(buf[1],[])
    for q in range(len(buf_root)-1):
        buf_path.append((str(min(int(buf_root[q]), int(buf_root[q + 1]))),
                              str(max(int(buf_root[q]), int(buf_root[q + 1])))))
    role.append(buf_path)
ans = 0
for i in range(2**(n-1)):
    cnt = 0
    flg = True
    for j in path.keys():
        path[j] = bool((1 << cnt) & i)
        cnt += 1
    for j in role:
        ss = 0
        for k in j:
            ss += path[k]
        if ss == 0:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


def dfs(start, goal, tree):
    """startからgoalまでの木上のpathを出力する"""
    q = deque([start])
    visited = {}
    visited[start] = -1
    while True:
        pos = q.pop()
        if pos == goal:
            break
        for child in tree[pos]:
            if child in visited:
                continue
            visited[child] = pos
            q.append(child)
    res = []
    pos = goal
    while True:
        par = visited[pos]
        if par == -1:
            break
        res.append((min(par, pos), max(par, pos)))
        pos = par
    return res


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
    memo[(min(a, b), max(a, b))] = i
  

li_path = [0] * m
for i in range(m):
    s, g = path[i]
    s -= 1
    g -= 1
    res = dfs(s, g)
    tmp = 0
    for j in res:
        tmp += (1 << memo[j])
    li_path[i] = tmp
  
ans = 0
for bit_state in range(1 << m):
    mask = 0
    cnt = 0
    for i in range(m):
        if bit_state & (1 << i):
            cnt += 1
            mask |= li_path[i]
    num_n = bin(mask).count("1")
    if cnt % 2 == 0:
        ans += 2 ** (n - 1 - num_n)
    else:
        ans -= 2 ** (n - 1 - num_n)
print(ans)

Submission status: Runtime Error

Solution code:
print(1)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

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)

Submission status: Runtime Error

Solution code:
import math
from collections import deque
 
v = []
path = []
 
 
def dfs(now, t, fa):
    if now == t:
        return 1
    for x, i in v[now]:
        if x == fa:
            continue
        if dfs(x, t, now):
            global path
            path.append(i)
            return 1
    return 0
 
 
b = []
 
n = int(input())
for i in range(n):
    v.append([])
for i in range(n-1):
    s = input().split(" ")
    x = int(s[0])-1
    y = int(s[1])-1
    v[x].append([y, i])
    v[y].append([x, i])
m = int(input())
for i in range(m):
    s = input().split(" ")
    x = int(s[0])-1
    y = int(s[1])-1
    path.clear()
    dfs(x, y, x)
    b.append(0)
    for z in path:
        b[i] |= (1 << z)
        # print('z='+str(z))
 
 
def count(x):
    cnt = 0
    while x > 0:
        if x % 2 == 1:
            cnt += 1
        x = x // 2
    return cnt
 
 
ans = 1 << (n-1)
for S in range(1, 1 << m):
    bb = 0
    for i in range(m):
        if (S >> i) & 1:
            bb |= b[i]
    cnt = n-1-count(bb)
    # print('bb='+str(bb))
    # print('cnt='+str(cnt))
    if count(S) % 2 == 1:
        ans -= (1 << cnt)
    else:
        ans += (1 << cnt)
 
print(ans)

Submission status: Runtime Error

Solution code:
import math

v = []
path = []
 
 
def dfs(now, t, fa):
    if now == t:
        return 1
    for x, i in v[now]:
        if x == fa:
            continue
        if dfs(x, t, now):
            global path
            path.append(i)
            return 1
    return 0
 
 
b = []
 
n = int(input())
for i in range(n):
    v.append([])
for i in range(n-1):
    s = input().split(" ")
    x = int(s[0])-1
    y = int(s[1])-1
    v[x].append([y, i])
    v[y].append([x, i])
m = int(input())
for i in range(m):
    s = input().split(" ")
    x = int(s[0])-1
    y = int(s[1])-1
    path.clear()
    dfs(x, y, x)
    b.append(0)
    for z in path:
        b[i] |= (1 << z)
        # print('z='+str(z))
 
 
def count(x):
    cnt = 0
    while x > 0:
        if x % 2 == 1:
            cnt += 1
        x //= 2
    return cnt
 
 
ans = 1 << (n-1)
for S in range(1, 1 << m):
    bb = 0
    for i in range(m):
        if (S >> i) & 1:
            bb |= b[i]
    cnt = n-1-count(bb)
    # print('bb='+str(bb))
    # print('cnt='+str(cnt))
    if count(S) % 2 == 1:
        ans -= (1 << cnt)
    else:
        ans += (1 << cnt)
 
print(ans)

Submission status: Runtime Error

Solution code:
def getpath(path, u, v,  visited, way):
  if u==v:
    return way
  for w in path[u]:
    if visited[w] == 0:
      visited_new = visited[:]
      visited_new[w] = 1
      way += [w]
      return getpath(path, w, v, visited_new, way)

def getans(black_list, uv):
  for row in uv:
    for i in range(N):
      if black_list[i] and  i in row:
        break
    else :return 0
  for i in range(N):
    if black_list[i]:
      black_new = black_list[:]
      black_new[i] = 0
      return getans(black_new, uv) + 1
  
  
N = int(input())
path = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  path[a-1] += [b-1]
  path[b-1] += [a-1]
M = int(input())
uv = []
for i in range(M):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  visited = [0]*N
  visited[u] = 1
  uv += [getpath(path, u, v, visited,[u])]

black_list = [1]*N
ans = getans(black_list, uv)
print(ans)

Submission status: Runtime Error

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(N)]
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: Runtime Error

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(N)]
for n in range(2**M):
    cnt = 0
    x = 0
    for i in range(M):
        if n&2**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: Runtime Error

Solution code:
N = int(input())

def count(a1,a2):
    res = 0
    for b in range(1,N+1):
        sb = str(b)
        if sb[0]==a2 and sb[-1]==a1:
            res += 1
    return res

d = {}
for a1 in range(1,10):
    for a2 in range(10):
        d[(str(a1),str(a2))] = count(str(a1),str(a2))

ans = 0
for a in range(1,N+1):
    sa = str(a)
    a1 = sa[0]
    a2 = sa[-1]
    ans += d[(a1,a2)]

print(ans)


#E
#%%
mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

da = defaultdict(lambda:0)
for i in range(N):
    d = prime_decomposition(A[i])
    for k in d:
        da[k] = max(da[k],d[k])
m = 1
for k in da:
    m *= pow(k,da[k],mod)
    m %= mod
ans = 0
for i in range(N):
    ans += m*pow(A[i],mod-2,mod)
    ans %= mod
print(ans)

#F
#%%
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(N)]
for n in range(2**M):
    cnt = 0
    x = 0
    for i in range(M):
        if n&2**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] += 2**(N-1-y)

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

print(ans)