25072번 - Destiny 다국어

Given a tree $T = (V,E)$ ($V$ is the set of vertices and $E$ is the set of edges) and a set of pairs of vertices $Q \subset V \times V$ satisfying for all $(u,v) \in Q$, $u \ne v$ and $u$ is an ancestor of $v$ on tree $T$, you are supposed to compute how many functions $f: E \to \{0, 1\}$ (i.e. for each edge $e \in E$, the value of $f(e)$ would be either $0$ or $1$) satisfies the condition for any $(u,v) \in Q$ there exists an edge $e$ on the path from $u$ to $v$ such that $f(e) = 1$. Output the answer modulo $998\,244\,353$.

The first line contains an input $n$ denoting the number of vertices in tree $T$. The nodes are numbered from 1 to $n$ and the root node is node 1. In the following $n-1$ lines, each line contains two integers separated by a space $x_i, y_i$ such that $1 \le x_i,y_i \le n$ denoting there exists an edge on the tree between node $x_i$ and $y_i$. There are no guarantees for the direction of the edge. The following line contains an integer $m$ denoting the size of $Q$. In the following $m$ lines, each line contains two integers separated by a space $u_i,v_i$ denoting $(u_i,v_i) \in Q$. There may be duplication, or in other words, there might exist some $i \ne j$ such that $u_i = u_j$ and $v_i = v_j$.

The output contains only an integer denoting the number of functions $f$ satisfying the condition above.

For all test cases, $n \le 5 \times 10^5$, $m \le 5 \times 10^5$. The input forms a tree, where for all $1 \le i \le m$, $u_i$ is the ancestor of $v_i$.