← 返回题目列表

AtCoder · abc152_f

F. 树和约束

中文机器翻译题面 查看原题

分数: 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

此输入中的树如下所示:

Figure

所有的 如果 Edge 满足 M 限制, 1 和 2 分别涂成(白,黑),(黑,白),或(黑,黑),所以答案是 3.


示例输入 2

2
1 2
1
1 2

示例输出 2

1

此输入中的树如下所示:

Figure

所有的 如果 Edge 满足 M 仅当 Edge 1 被涂成黑色,所以答案是 1.


示例输入 3

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

示例输出 3

9

此输入中的树如下所示:

Figure


示例输入 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

此输入中的树如下所示:

Figure