3466. [NOI 2020]命运

【题目描述】

提示：我们在题目描述的最后一段提供了一份简要的、形式化描述的题面。

在遥远的未来，物理学家终于发现了时间和因果的自然规律。即使在一个人出生前，我们也可以通过理论分析知晓他或她人生的一些信息，换言之，物理学允许我们从一定程度上“预言”一个人的“命运”。

简单来说，一个人的命运是一棵由时间点构成的有根树 T：树的根结点代表着出生，而叶结点代表着死亡。每个非叶结点 u 都有一个或多个孩子 $v_1,v_2,\cdots,v_{c_u}$，表示这个人在 u 所代表的时间点做出的$c_u$个不同的选择可以导向的不同的可能性。形式化的，一个选择就是树上的一条边 (u,vi)，其中 u 是 vi 的父结点。

一个人的一生是从出生（即根结点）到死亡（即某一个叶子结点）的一条不经过重复结点的路径，这条路径上任何一个包含至少一条边的子路径都是这个人的一段人生经历，而他或她以所有可能的方式度过一生，从而拥有的所有人生经历，都被称为潜在的人生经历。换言之，所有潜在的人生经历就是所有 u 到 v 的路径，满足 u,v∈T，u≠v，并且 u 是 v 的祖先。在数学上，这样一个潜在的人生经历被记作有序对 (u,v)，树 T 所有潜在的人生经历的集合记作 $P_T$。

物理理论不仅允许我们观测代表命运的树，还能让我们分析一些潜在的人生经历是否是“重要”的。一个人所作出的每一个选择——即树上的每一条边——都可能是重要或不重要的。一段潜在的人生经历被称为重要的，当且仅当其对应的路径上存在一条边是重要的。我们可以观测到一些潜在的人生经历是重要的：换言之，我们可以观测得到一个集合 Q⊆$P_T$，满足其中的所有潜在的人生经历 (u,v)∈Q 都是重要的。

树 T 的形态早已被计算确定，集合 Q 也早已被观测得到，一个人命运的不确定性已经大大降低了。但不确定性仍然是巨大的——来计算一下吧，对于给定的树 T 和集合 Q，存在多少种不同的方案确定每条边是否是重要的，使之满足所观测到的 Q 所对应的限制：即对于任意 (u,v)∈Q，都存在一条 u 到 v 路径上的边被确定为重要的。

形式化的：

给定一棵树 T=(V,E) 和点对集合 Q⊆V×V ，满足对于所有 (u,v)∈Q，都有 u≠v，并且 u 是 v 在树 T 上的祖先。其中 V 和 E 分别代表树 T 的结点集和边集。求有多少个不同的函数 f : E→{0,1}（将每条边 e∈E 的 f(e) 值置为 0 或 1），满足对于任何 (u,v)∈Q，都存在 u 到 v 路径上的一条边 e 使得 f(e)=1。由于答案可能非常大，你只需要输出结果对 998,244,353（一个素数）取模的结果。

【输入格式】

第一行包含一个正整数 n，表示树 T 的大小，树上结点从 1 到 n 编号，1 号结点为根结点；

接下来 n−1 行每行包含空格隔开的两个数 xi,yi，满足 1≤xi,yi≤n，表示树上的结点 xi 和 yi 之间存在一条边，但并不保证这条边的方向；

接下来一行包含一个非负整数 m，表示所观测得到信息的条数。

接下来 m 行每行包含空格隔开的两个数 ui,vi，表示 (ui,vi)∈Q。

数据可能包含重复的信息，换言之可能存在 i≠j，满足 ui=uj 且 vi=vj。输入数据规模和限制参见本题末尾的表格。

【输出格式】

输出仅一行一个整数，表示方案数对 998,244,353取模的结果。

【样例输入1】

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

【样例输出1】

10

【样例1解释】

共有 16 种方案，其中不满足题意的方案有以下 6 种：

(1,2),(2,3),(3,5) 确定为不重要，(3,4) 确定为重要：集合 Q 中没有限制被满足。

(1,2),(2,3),(3,4),(3,5) 确定为不重要：集合 Q 中没有限制被满足。

(1,2),(2,3) 确定为不重要，(3,4),(3,5) 确定为重要：集合 Q 中 (1,3) 没被满足。

(1,2),(2,3),(3,4) 确定为不重要，(3,5) 确定为重要：集合 Q 中 (1,3) 没被满足。

(2,3),(3,5) 确定为不重要，(1,2),(3,4) 确定为重要：集合 Q 中 (2,5) 没被满足。

(2,3),(3,4),(3,5) 确定为不重要，(1,2) 确定为重要：集合 Q 中 (2,5) 没被满足。

其他方案下，集合 Q 中的限制都被满足了。

【样例输入2】

15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13

【样例输出2】

960

【数据范围】

全部数据满足：n≤5×10^5，m≤5×10^5。输入构成一棵树，并且对于 1≤i≤m，ui 始终为 vi 的祖先结点。

完全二叉树：在本题中，每个非叶结点都有左右子结点，且所有叶子结点深度相同的树称为满二叉树；将满二叉树中的结点按照从上到下、从左向右的顺序编号，编号最小的若干个结点形成的树称为完全二叉树。

【来源】

NOI2020 Day1 Task2