Tree and Constraints

题目描述

我们有一棵顶点编号为 $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

2
1 2
1
1 2

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 < v_i \leq N 如果 $i \not= j$，要么 $u_i \not= u_j$，要么 $v_i \not= v_j$ 输入中的所有值均为整数。输入中的树如下所示：



如果边 $1$ 和 $2$ 分别被涂成（白, 黑）、（黑, 白）或（黑, 黑），则所有 $M$ 条限制都会被满足，所以答案是 $3$。
输入中的树如下所示：



只有当边 $1$ 被涂成黑色时才会满足所有 $M$ 条限制，所以答案是 $1$。
输入中的树如下所示：




输入中的树如下所示：

标签: AtCoder|abc152F

来源

AtCoder|abc152F