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$ 个限制条件的涂色方式的数量。

## 限制条件 - $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 翻译