A7518. [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$ 的路径上，至少有一条边被涂成黑色。
现在要对这棵树的每一条边分别涂成白色或黑色。这样的涂色方式共有 $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$
> $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
3 1 2 2 3 1 1 3
输出 #1
3
输入 #2
2 1 2 1 1 2
输出 #2
1
输入 #3
5 1 2 3 2 3 4 5 3 3 1 3 2 4 2 5
输出 #3
9
输入 #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
该输入对应的树如下图所示。
- $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
该输入对应的树如下图所示。
