分数: 600 点
问题陈述
我们有一棵树 N 顶点编号 1 to N。
的 i此树中的第一条边连接顶点 a_i 和顶点 b_i.
考虑将这些边缘涂成白色或黑色。有 2^{N-1} 这样的方式来绘制边缘。其中,满足以下全部条件的有多少 M 限制?
- 的 i-th (1 \leq i \leq M) 限制由两个整数表示 u_i 和 v_i,表示连接 Vertex 的路径 u_i 和顶点 v_i 必须至少包含一个涂成黑色的边缘。
约束
- 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
- If i \not= j,或者 u_i \not=u_j or v_i\not=v_j
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M
输出
打印满足所有条件的绘制边缘的方法数 M 条件。
示例输入 1
3 1 2 2 3 1 1 3
示例输出 1
3
此输入中的树如下所示:
所有的
如果 Edge 满足 M 限制, 1 和 2 分别涂成(白,黑),(黑,白),或(黑,黑),所以答案是 3.
示例输入 2
2 1 2 1 1 2
示例输出 2
1
此输入中的树如下所示:
所有的
如果 Edge 满足 M 仅当 Edge 1 被涂成黑色,所以答案是 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
此输入中的树如下所示: