← 返回题目
题库练习 [ABC152F] Tree and Constraints
← 上一题 下一题 →

A7518 | [ABC152F] Tree and Constraints

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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

输入输出样例

输入 #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
C++ 编辑器
输入
输出