AT_abc152_f [ABC152F] Tree and Constraints

题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。这棵树的第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。

现在要对这棵树的每一条边分别涂成白色或黑色。这样的涂色方式共有 $2^{N-1}$ 种。请你计算，有多少种涂色方式满足以下 $M$ 个限制条件：

• 第 $i$ 个限制由两个整数 $u_i$ 和 $v_i$ 给出，表示从顶点 $u_i$ 到顶点 $v_i$ 的路径上，至少有一条边被涂成黑色。

输入格式

输入按以下格式从标准输入读入。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

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

输入输出样例 #1

输入 #1

3
1 2
2 3
1
1 3

输出 #1

3

输入输出样例 #2

输入 #2

2
1 2
1
1 2

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

9

输入输出样例 #4

输入 #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

输出 #4

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 < v_i \leq N$
• 若 $i \neq j$，则 $u_i \neq u_j$ 或 $v_i \neq v_j$
• 所有输入均为整数。

样例解释 1

该输入对应的树如下图所示。

将边 $1$ 和边 $2$ 分别涂为（白，黑）、（黑，白）、（黑，黑）时，均能满足全部 $M$ 个限制条件。因此答案为 $3$。

样例解释 2

该输入对应的树如下图所示。

只有当边 $1$ 被涂成黑色时，才能满足全部 $M$ 个限制条件。因此答案为 $1$。

样例解释 3

该输入对应的树如下图所示。

样例解释 4

该输入对应的树如下图所示。

由 ChatGPT 4.1 翻译