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:


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

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

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


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

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

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

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

            for wtmp in e[p]:
                for ttt in way[s][p]:
                    w.append(ttt)
                if w[wtmp[1]] == 1:
                    continue
                w[wtmp[1]] = 1
                stack.append([wtmp[0],w])

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



    

        



main()

Submission status: Runtime Error

Solution code:
#入力
N=int(input())
ab=[]
#頂点1,3,4が直接つながっている時G[1]=[3,4],G[3]=[1,4],G[4]=[1,3]となるグラフ表現
G=[[] for i in range(N+1)]
for i in range(N-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

M=int(input())
print(M)
ans=2**(N-1)


for k in range(M):
    u,v=map(int,input().split())
    start=u
    goal=v
    #ノードが探索済みか否かを判別するリスト
    #used[6]=1ならばノード６は探索済み
    used=[0 for y in range(N+1)]
    d=[100 for y in range(N+1)]
    
    queue=[]
    queue.append(start)
    d[start]=0
    print(queue)

    while len(queue)>0:
        #キューからノードを取り出して、探索済みにする
        num=queue.pop(0)
        used[num]=1
        
        #現在のノードから伸びている枝の数だけ探索
        for j in range(1,len(G[num])+1):
            #探索するノードが未探索かの判定
            if used[G[num][j]]==0:
                d[G[num][j]]=d[num]+1
                queue.append(G[num][j])
            if G[num][j]==goal:
                break
        break
    
    ans-=2**d[goal-1]
    
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define REP(i, n) for ( int i = 0; i < (n); i++ )

int N;
vector<vector<int> > G;
using P = pair<int, int>;
map<P, int> ch;

vector<int> pre;
void dfs(int p, int v) {  
  for ( int u: G[v] ) {    
    if ( u == p ) continue;    
    pre[u] = v;    
    dfs(v, u);    
  }
}

vector<int> path(int u, int v) {
  // cout << 'a' << endl;
  pre.resize(N, -1);  
  dfs(-1, u);
  // cout << 'a' << endl;
  vector<int> ret;
  int now = v;
  while ( pre[now] != -1 ) {
    ret.push_back(ch[P(v, pre[now])]);    
    now = pre[now];
  }

  return ret;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  
  cin >> N;
  G.resize(N);

  for ( int i = 0; i < N-1; i++ ) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
    ch[P(a, b)] = i;
    ch[P(b, a)] = i;    
  }

  int M;
  cin >> M;

  vector<int> mask(M, 0);
  for ( int i = 0; i < M; i++ ) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    vector<int> tmp = path(u, v);
    for ( int j: tmp ) mask[i] |= (1LL<<j);
    // cout << bitset<3>(mask[i]) << endl;
  }

  int ans = 1;
  for ( int i = 0; i < N-1; i++ ) ans *= 2;
  for ( int i = 1; i < (1<<M); i++ ) {
    vector<int> used(N, 0);
    int b = 0;    
    for ( int j = 0; j < M; j++ ) {
      if ( i&(1<<j) ) b |= mask[j];      
    }
    int cnt = N - __builtin_popcount(b) - 1;
    int tmp = 1;
    for ( int i = 0; i < cnt; i++ ) tmp *= 2;
    if ( __builtin_popcount(i) % 2 == 0 ) ans += tmp;
    else ans -= tmp;    
  }

  cout << ans << endl;
  
  return 0;
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
N = N - 1
arr = [[N]]
arr1 = [[N]]
for i in range(N):
	print(i)
	arr[i] = input()
	arr1[i] = [int(i) for i in arr[i].split(' ')]
M = int(input())
M = M - 1 
arr2 = [2][M]
for j in range(M):
	arr2[j] = input()
	arr1[j + i] = [int(j) for j in arr2[j].split(' ')]
print(arr)

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[w] = 1
      way += [w]
      return getpath(path, w, v, visited, 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:
n=int(input())
g=[[] for i in range(n)]
tr=[set([]) for i in range(n-1)]
l=[]
for i in range(n-1):
    a,b=map(int,input().split())
    l.append([a-1,b-1])
    g[a-1].append(b-1)
    g[b-1].append(a-1)
m=int(input())
p=[]
for i in range(m):
    c,d=map(int,input().split())
    p.append([c-1,d-1])
for i in range(m):
    q=[[p[i][0]]]
    goal=p[i][1]
    v=[0]*n
    v[p[i][0]]=1
    df=0
    while True:
        qq=q.pop(0)
        go=qq[-1]
        for j in g[go]:
            if j==goal:
                sg=qq+[j]
                df=1
                break      
            if v[j]==0:
                q.append(qq+[j])
                v[j]=1
        if df==1:
            break
    for ii in range(len(sg)-1):
        for j in range(n-1):
            if l[j]==[sg[ii],sg[ii+1]] or l[j]==[sg[ii+1],sg[ii]]:
                tr[j].add(i)
                break
op=[[0],[1]]
for i in range(m-1):
    tmp=[]
    for j in op:
        tmp.append(j+[0])
        tmp.append(j+[1])
    op=tmp
zop=[]
for i in op:
    tmp=set([])
    for j in range(m):
        if i[j]==1:
            tmp.add(j)
    zop.append(tmp)
zz=[0]*(len(zop))
for i in tr:
    for j in range(len(zop)):
        if i==z[j]:
            zz[j]+=1

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;

bool s[22][52];
bool uni[52];

int main() {
	int n; cin >> n;
	vector<vector<pair<int, int>>> edg(50, vector<pair<int, int>>(50));
	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;
		u--; v--;
		edg[u][v] = edg[v][u] = { 1, i };
	}
	int m; cin >> m;
	auto func = [&](auto& self, int t, int a, int from, int goal) -> bool {
		if (a == goal) return true;
		for (int i = 0; i < n; i++) {
			if (i == from) continue;
			if (edg[a][i].first == 0) continue;
			bool ret = self(self, t, i, a, goal);
			if (ret) {
				s[t][edg[a][i].second] = true;
				return true;
			}
		}
		return false;
	};

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		a--; b--;
		func(func, i, a, -1, b);
	}

	ll ng = 0;
	for (int t = 1; t < (1 << m); t++) {
		int bcnt = 0;
		for (int i = 0; i < m; i++) {
			bcnt += (t >> i) & 1;
		}
		for (int i = 0; i < n; i++) {
			uni[i] = false;
		}
		for (int c = 0; c < m; c++) {
			if (!((t >> c) & 1)) continue;
			for (int i = 0; i < n; i++) {
				uni[i] |= s[c][i];
			}
		}
		ll pcnt = 0;
		for (int i = 0; i < n; i++) {
			pcnt += uni[i];
		}
		ll c = 1LL << (n - 1 - pcnt);
		if (!(bcnt & 1)) c *= -1;
		ng += c;
	}
	cout << (1LL << (n - 1)) - ng << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(cur, pre, g, par, od):
    par[cur] = pre
    od.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, par, od)

par = [-1] * n
od = []
dfs(0, -1, g, par, od)

def lca(a, b, par):
    ps = set()
    q = a
    while q != -1:
        ps.add(q)
        q = par[q]
    while b != -1:
        if b in ps:
            return b
        b = par[b]
    raise

m = ni()
cons = [0] * n
for i in range(m):
    u, v = na()
    u -= 1
    v -= 1
    lc = lca(u, v, par)
    while u != lc:
        cons[u] |= 1<<i
        u = par[u]
    while v != lc:
        cons[v] |= 1<<i
        v = par[v]

def st(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] += b[j]
    return b

def ist(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] -= b[j]
    return b

dp = [None for _ in range(n)]
for i in range(n-1,-1,-1):
    cur = od[i]
    my = [0] * (1<<m)
    my[0] = 1
    if cur != 0:
        my[cons[cur]] += 1
    my = st(my, m)

    for e in g[cur]:
        if e == par[cur]: continue
        for j in range(1<<m):
            my[j] = my[j] * dp[e][j]
    dp[i] = my

    # dp[i] = ist(my, m)

dp[0] = ist(dp[0], m)

print(dp[0][(1<<m)-1])

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(cur, pre, g, par, od):
    par[cur] = pre
    od.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, par, od)

par = [-1] * n
od = []
dfs(0, -1, g, par, od)

def lca(a, b, par):
    ps = set()
    q = a
    while q != -1:
        ps.add(q)
        q = par[q]
    while b != -1:
        if b in ps:
            return b
        b = par[b]
    raise

m = ni()
cons = [0] * n
for i in range(m):
    u, v = na()
    u -= 1
    v -= 1
    lc = lca(u, v, par)
    while u != lc:
        cons[u] |= 1<<i
        u = par[u]
    while v != lc:
        cons[v] |= 1<<i
        v = par[v]

def st(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] += b[j]
    return b

def ist(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] -= b[j]
    return b

mod = 1000000007
dp = [None for _ in range(n)]
for i in range(n-1,-1,-1):
    cur = od[i]
    my = [0] * (1<<m)
    my[0] = 1
    if cur != 0:
        my[cons[cur]] += 1
    my = st(my, m)

    for e in g[cur]:
        if e == par[cur]: continue
        # q = st(dp[e], m)
        for j in range(1<<m):
            my[j] = my[j] * dp[e][j] % mod
    dp[i] = my

    # dp[i] = ist(my, m)

dp[0] = ist(dp[0], m)

print(dp[0][(1<<m)-1])

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(cur, pre, g, par, od):
    par[cur] = pre
    od.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, par, od)

par = [-1] * n
od = []
dfs(0, -1, g, par, od)

def lca(a, b, par):
    ps = set()
    q = a
    while q != -1:
        ps.add(q)
        q = par[q]
    while b != -1:
        if b in ps:
            return b
        b = par[b]
    raise

m = ni()
cons = [0] * n
for i in range(m):
    u, v = na()
    u -= 1
    v -= 1
    lc = lca(u, v, par)
    while u != lc:
        cons[u] |= 1<<i
        u = par[u]
    while v != lc:
        cons[v] |= 1<<i
        v = par[v]

def st(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] += b[j]
    return b

def ist(b, m):
    # b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] -= b[j]
    return b

mod = 1000000007
dp = [None for _ in range(n)]
for i in range(n-1,-1,-1):
    cur = od[i]
    my = [0] * (1<<m)
    my[0] = 1
    if cur != 0:
        my[cons[cur]] += 1
    my = st(my, m)

    for e in g[cur]:
        if e == par[cur]: continue
        q = st(dp[e], m)
        for j in range(1<<m):
            my[j] = my[j] * q[j] % mod

    dp[i] = ist(my, m)

print(dp[0][(1<<m)-1])

Submission status: Runtime Error

Solution code:
from copy import copy
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)

def dfs(cur, pre, g, par, od):
    par[cur] = pre
    od.append(cur)
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, par, od)

par = [-1] * n
od = []
dfs(0, -1, g, par, od)

def lca(a, b, par):
    ps = set()
    q = a
    while q != -1:
        ps.add(q)
        q = par[q]
    while b != -1:
        if b in ps:
            return b
        b = par[b]
    raise

m = ni()
cons = [0] * n
for i in range(m):
    u, v = na()
    u -= 1
    v -= 1
    lc = lca(u, v, par)
    while u != lc:
        cons[u] |= 1<<i
        u = par[u]
    while v != lc:
        cons[v] |= 1<<i
        v = par[v]

def st(a, m):
    b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] += b[j]
    return b

def ist(a, m):
    b = copy(a)
    for i in range(m):
        for j in range(1<<m):
            if (j>>i&1) == 0:
                b[j|1<<i] -= b[j]
    return b

mod = 1000000007
dp = [None for _ in range(n)]
for i in range(n-1,-1,-1):
    cur = od[i]
    my = [0] * (1<<m)
    my[0] = 1
    if cur != 0:
        my[cons[cur]] += 1
    my = st(my, m)

    for e in g[cur]:
        if e == par[cur]: continue
        q = st(dp[e], m)
        for j in range(1<<m):
            my[j] = my[j] * q[j] % mod

    dp[i] = ist(my, m)

print(dp[0][(1<<m)-1])