← 返回题目

题库练习「NOI2020」命运

← 上一题下一题 →

A5929 | $「NOI2020」命运$

时间限制2s

内存限制1024MB

通过 / 提交0/0

题目描述

**提示**：我们在题目描述的最后一段提供了一份简要的、形式化描述的题面。 在遥远的未来，物理学家终于发现了时间和因果的自然规律。即使在一个人出生前，我们也可以通过理论分析知晓他或她人生的一些信息，换言之，物理学允许我们从一定程度上“预言”一个人的“命运”。 简单来说，一个人的命运是一棵由时间点构成的有根树 $T$：树的根结点代表着出生，而叶结点代表着死亡。每个非叶结点 $u$ 都有一个或多个孩子 $v_1, v_2, \dots, v_{c_u}$，表示这个人在 $u$ 所代表的时间点做出的 $c_u$ 个不同的选择可以导向的不同的可能性。形式化的，一个**选择**就是树上的一条边 $(u, v_i)$，其中 $u$ 是 $v_i$ 的父结点。 一个人的一生是从出生（即根结点）到死亡（即某一个叶子结点）的一条不经过重复结点的路径，这条路径上任何一个包含至少一条边的子路径都是这个人的一段**人生经历**，而他或她以所有可能的方式度过一生，从而拥有的所有人生经历，都被称为**潜在的人生经历**。换言之，所有潜在的人生经历就是所有 $u$ 到 $v$ 的路径，满足 $u, v \in T$，$u\neq v$，并且 $u$ 是 $v$ 的祖先。在数学上，这样一个潜在的人生经历被记作有序对 $(u, v)$，树 $T$ 所有潜在的人生经历的集合记作 $\mathcal P_T$。 物理理论不仅允许我们观测代表命运的树，还能让我们分析一些潜在的人生经历是否是“重要”的。一个人所作出的每一个选择——即树上的每一条边——都可能是**重要**或**不重要**的。一段潜在的人生经历被称为重要的，当且仅当其对应的路径上存在一条边是重要的。我们可以观测到一些潜在的人生经历是重要的：换言之，我们可以观测得到一个集合 $\mathcal Q\subseteq \mathcal P_T$ ，满足其中的所有潜在的人生经历 $(u, v) \in \mathcal Q$ 都是重要的。 树 $T$ 的形态早已被计算确定，集合 $Q$ 也早已被观测得到，一个人命运的不确定性已经大大降低了。但不确定性仍然是巨大的——来计算一下吧，对于给定的树 $T$ 和集合 $Q$，存在多少种不同的方案确定每条边是否是重要的，使之满足所观测到的 $Q$ 所对应的限制：即对于任意 $(u, v) \in \mathcal Q$，都存在一条 $u$ 到 $v$ 路径上的边被确定为重要的。 **形式化的**：给定一棵树 $T = (V,E)$ 和点对集合 $\mathcal Q \subseteq V\times V$，满足对于所有 $(u, v) \in \mathcal Q$，都有 $u \neq v$，并且 $u$ 是 $v$ 在树 $T$ 上的祖先。其中 $V$ 和 $E$ 分别代表树 $T$ 的结点集和边集。求有多少个不同的函数 $f : E \rightarrow \{0, 1\}$（将每条边 $e \in E$ 的 $f(e)$ 值置为 $0$ 或 $1$），满足对于任何 $(u, v) \in \mathcal Q$，都存在 $u$ 到 $v$ 路径上的一条边 $e$ 使得 $f(e) = 1$。由于答案可能非常大，你只需要输出结果对 $998,244,353$（一个素数）取模的结果。

输入格式

从文件 destiny.in 中读入数据。 - 第一行包含一个正整数 $n$，表示树 $T$ 的大小，树上结点从 $1$ 到 $n$ 编号，$1$ 号结点为根结点； - 接下来 $n - 1$ 行每行包含空格隔开的两个数 $x_i, y_i$，满足 $1\le x_i, y_i \le n$，表示树上的结点 $x_i$ 和 $y_i$ 之间存在一条边，但并不保证这条边的方向； - 接下来一行包含一个非负整数 $m$，表示所观测得到信息的条数。 - 接下来 $m$ 行每行包含空格隔开的两个数 $u_i,v_i$，表示 $(u_i, v_i) \in \mathcal Q$。**请注意**：输入数据可能包含重复的信息，换言之可能存在 $i\neq j$，满足 $u_i = u_j$ 且 $v_i = v_j$。 输入数据规模和限制参见本题末尾的表格。

输出格式

输出到文件 destiny.out 中。 - 输出仅一行一个整数，表示方案数对 $998, 244, 353$ 取模的结果。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

| 测试点编号 | $n$ | $m$ | $T$ 为完全二叉树 | | :----------: | :------------------: | :------------------: | :----------------: | | $1$ | $\le10$ | $\le10 $ | 否 | | $2$ | $\le10$ | $\le10 $ | 否 | | $3$ | $\le10$ | $\le10 $ | 否 | | $4$ | $\le10$ | $\le10 $ | 否 | | $5$ | $\le 500$ | $\le15$ | 否 | | $6$ | $\le 10^4$ | $\le10$ | 否 | | $7$ | $\le 10^5$ | $\le16$ | 否 | | $8$ | $\le 5\times 10^5$ | $\le16$ | 否 | | $9$ | $\le 10^5$ | $\le22$ | 否 | | $10$ | $\le 5\times 10^5$ | $\le22$ | 否 | | $11$ | $\le 600$ | $\le 600 $ | 否 | | $12$ | $\le 1000$ | $\le 1000 $ | 否 | | $13$ | $\le 2000$ | $\le 5\times 10^5$ | 否 | | $14$ | $\le 2000$ | $\le 5\times 10^5$ | 否 | | $15$ | $\le 5\times 10^5$ | $\le 2000$ | 否 | | $16$ | $\le 5\times 10^5$ | $\le 2000$ | 否 | | $17$ | $\le 10^5$ | $\le 10^5$ | 是 | | $18$ | $\le 10^5$ | $\le 10^5$ | 是 | | $19$ | $\le 5\times 10^4$ | $\le 10^5$ | 否 | | $20$ | $\le 8\times 10^4$ | $\le 10^5$ | 否 | | $21$ | $\le 10^5$ | $\le 5\times 10^5$ | 否 | | $22$ | $\le 10^5$ | $\le 5\times 10^5$ | 否 | | $23$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | 否 | | $24$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | 否 | | $25$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | 否 | **全部数据满足**：$n\le 5\times 10^5$，$m\le 5\times 10^5$。输入构成一棵树，并且对于 $1\le i\le m$，$u_i$ 始终为 $v_i$ 的祖先结点。 **完全二叉树**：在本题中，每个非叶结点都有左右子结点，且所有叶子结点深度相同的树称为满二叉树；将满二叉树中的结点按照从上到下、从左向右的顺序编号，编号最小的若干个结点形成的树称为完全二叉树。

C++ 编辑器

输入

输出