F - 树和约束

得分：600分

题目描述

我们有一棵有$N$个顶点的树，顶点编号为1到$N$。

第$i$条边连接顶点$a_i$和顶点$b_i$。

考虑对每一条边涂上黑色或者白色。总共有$2^{N-1}$种方式来涂色。在这些方式中，有多少种满足以下的$M$个限制条件？

• 第$i$个限制条件（$1 \leq i \leq M$）由两个整数$u_i$和$v_i$表示，表示顶点$u_i$和顶点$v_i$之间的路径必须至少包含一条黑色的边。

约束条件

• $2 \leq N \leq 50$
• $1 \leq a_i,b_i \leq N$
• 给出的图是一棵树
• $1 \leq M \leq \min(20,\frac{N(N-1)}{2})$
• $1 \leq u_i < v_i \leq N$
• 如果$i \neq j$，要么$u_i \neq u_j$，要么$v_i \neq v_j$
• 输入中的所有值都是整数

输入

输入从标准输入中得到，格式如下：

$N$

$a_1$ $b_1$

...

$a_{N-1}$ $b_{N-1}$

$M$

$u_1$ $v_1$

...

$u_M$ $v_M$

输出

输出满足所有$M$个条件的涂色方式的数量。

3
1 2
2 3
1
1 3

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$.

2
1 2
1
1 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$.

5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5

9

The tree in this input is shown below:

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

62

The tree in this input is shown below: