P6773 [NOI2020] Destiny

**Hint**: In the last paragraph of the statement, we provide a brief, formal description. In the distant future, physicists finally discovered the natural laws of time and causality. Even before a person is born, we can learn some information about his or her life through theoretical analysis. In other words, physics allows us to “predict” a person’s “destiny” to some extent. Simply put, a person’s destiny is a rooted tree $T$ made up of time points: the root represents birth, and the leaves represent death. Each non-leaf node $u$ has one or more children $v_1, v_2,\dots, v_{c_u}$, meaning that at the time point represented by $u$, the person can make $c_u$ different choices, leading to different possibilities. Formally, a choice is an edge $(u, v_i)$ in the tree, where $u$ is the parent of $v_i$. A person’s life is a path from birth (the root) to death (some leaf), without repeating nodes. Any subpath of this path that contains at least one edge is a **life experience**. All life experiences that he or she could have, by living the life in all possible ways, are called **potential life experiences**. In other words, all potential life experiences are all paths from $u$ to $v$ such that $u, v \in T$, $u \neq v$, and $u$ is an ancestor of $v$. Mathematically, such a potential life experience is written as an ordered pair $(u, v)$, and the set of all potential life experiences of the tree $T$ is denoted by $\mathcal P_T$. Physical theory not only allows us to observe the tree that represents destiny, but also lets us analyze whether some potential life experiences are “important”. Each choice a person makes—namely, each edge of the tree—may be **important** or **unimportant**. A potential life experience is called important if and only if there exists at least one important edge on the corresponding path. We can observe that some potential life experiences are important. In other words, we can observe a set $\mathcal Q \subseteq \mathcal P_T$, such that every potential life experience $(u, v) \in \mathcal Q$ is important. The shape of the tree $T$ has long been computed and fixed, and the set $\mathcal Q$ has also been observed, so the uncertainty of a person’s destiny has been greatly reduced. But the uncertainty is still huge—let us compute it. For a given tree $T$ and set $\mathcal Q$, how many different ways are there to decide whether each edge is important, such that the observed constraints from $\mathcal Q$ are satisfied? That is, for every $(u, v) \in \mathcal Q$, there must be an edge on the path from $u$ to $v$ that is determined to be important. **Formally**: Given a tree $T = (V, E)$ and a set of pairs $\mathcal Q \subseteq V \times V$, such that for all $(u, v) \in \mathcal Q$, we have $u \neq v$ and $u$ is an ancestor of $v$ in the tree $T$. Here, $V$ and $E$ are the node set and edge set of $T$, respectively. Find the number of different functions $f : E \to \{0, 1\}$ (assigning each edge $e \in E$ a value $f(e)$ equal to $0$ or $1$), such that for any $(u, v) \in \mathcal Q$, there exists an edge $e$ on the path from $u$ to $v$ with $f(e) = 1$. Since the answer may be very large, you only need to output it modulo $998,244,353$ (a prime number).

Read from standard input. The first line contains a positive integer $n$, denoting the size of the tree $T$. The nodes are numbered from $1$ to $n$, and node $1$ is the root. In the next $n - 1$ lines, each line contains two integers $x_i, y_i$ separated by spaces, with $1 \leq x_i, y_i \leq n$, indicating that there is an edge between nodes $x_i$ and $y_i$, but the direction of this edge is not guaranteed. The next line contains a non-negative integer $m$, denoting the number of observed pieces of information. In the next $m$ lines, each line contains two integers $u_i, v_i$ separated by spaces, indicating $(u_i, v_i) \in \mathcal Q$. **Note**: The input may contain duplicate information. In other words, there may exist $i \neq j$ such that $u_i = u_j$ and $v_i = v_j$. The input size and constraints can be found in the table at the end of the statement.

Write to standard output. Output a single line with one integer, the number of valid assignments modulo $998,244,353$.

#### Explanation for Sample 1 There are $16$ assignments in total. Among them, the following $6$ do not satisfy the requirements: - Set $(1, 2),(2, 3),(3, 5)$ to unimportant, and set $(3, 4)$ to important: no constraint in $\mathcal Q$ is satisfied. - Set $(1, 2),(2, 3),(3, 4),(3, 5)$ to unimportant: no constraint in $\mathcal Q$ is satisfied. - Set $(1, 2),(2, 3)$ to unimportant, and set $(3, 4),(3, 5)$ to important: in $\mathcal Q$, $(1, 3)$ is not satisfied. - Set $(1, 2),(2, 3),(3, 4)$ to unimportant, and set $(3, 5)$ to important: in $\mathcal Q$, $(1, 3)$ is not satisfied. - Set $(2, 3),(3, 5)$ to unimportant, and set $(1, 2),(3, 4)$ to important: in $\mathcal Q$, $(2, 5)$ is not satisfied. - Set $(2, 3),(3, 4),(3, 5)$ to unimportant, and set $(1, 2)$ to important: in $\mathcal Q$, $(2, 5)$ is not satisfied. - Under other assignments, all constraints in $\mathcal Q$ are satisfied. #### Sample 3 See destiny/destiny3.in and destiny/destiny3.ans in the contestant directory. #### Sample 4 See destiny/destiny4.in and destiny/destiny4.ans in the contestant directory. | Test Point ID | $n$ | $m$ | $T$ is a complete binary tree | | :-: | :-: | :-: | :-: | | $1\sim 4$ | $\le 10$ | $\le 10$ | No | | $5$ | $\le 500$ | $\le 15$ | No | | $6$ | $\le 10^4$ | $\le 10$ | No | | $7$ | $\le 10^5$ | $\le 16$ | No | | $8$ | $\le 5\times 10^5$ | $\le 16$ | No | | $9$ | $\le 10^5$ | $\le 22$ | No | | $10$ | $\le 5\times 10^5$ | $\le 22$ | No | | $11$ | $\le 600$ | $\le 600$ | No | | $12$ | $\le 10^3$ | $\le 10^3$ | No | | $13\sim 14$ | $\le 2\times 10^3$ | $\le 5\times 10^5$ | No | | $15\sim 16$ | $\le 5\times 10^5$ | $\le 2\times 10^3$ | No | | $17\sim 18$ | $\le 10^5$ | $\le 10^5$ | Yes | | $19$ | $\le 5\times 10^4$ | $\le 10^5$ | No | | $20$ | $\le 8\times 10^4$ | $\le 10^5$ | No | | $21\sim 22$ | $\le 10^5$ | $\le 5\times 10^5$ | No | | $23\sim 25$ | $\le 5\times 10^5$ | $\le 5\times 10^5$ | No | --- ### Constraints **All testdata satisfy**: $n \leq 5 \times 10^5$, $m \leq 5 \times 10^5$. The input forms a tree, and for $1 \leq i \leq m$, $u_i$ is always an ancestor of $v_i$. **Complete binary tree**: In this problem, a full binary tree is a tree in which every non-leaf node has left and right children, and all leaf nodes have the same depth. Number the nodes of a full binary tree from top to bottom and from left to right; the tree formed by the first few nodes with the smallest indices is called a complete binary tree. Translated by ChatGPT 5