树与限制

题目描述

有一棵具有 $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$ 的路径中包含的边中,必须至少有一条被涂成黑色。

输入格式

输入按以下格式从标准输入给出:

$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

这个输入中的树如下所示。

当边 $1$ 和边 $2$ 分别涂成 (白,黑)、(黑,白)、(黑,黑) 时,可以满足所有 $M$ 个约束。

因此答案为 $3$。

2
1 2
1
1 2

1

这个输入中的树如下所示。

只有把边 $1$ 涂成黑色时,才能满足所有 $M$ 个约束。

因此答案为 $1$。

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

9

这个输入中的树如下所示。

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

这个输入中的树如下所示。

数据范围

• $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 \lt v_i \leq N$
• 若 $i \not= j$,则 $u_i \not=u_j$ 或 $v_i\not=v_j$
• 输入均为整数。