P6799 "StOI-2" Independent Set

Given an unrooted tree with $n$ nodes and $m$ paths on the tree, find the total number of "independent set" selections formed from these $m$ paths. Since the answer may be very large, you only need to output it modulo $998,244,353$. An "independent set" here means a set of paths such that there does **not** exist a pair of paths in the set that intersect (share at least one common node) on the tree. In particular, the empty set and any set containing only one path are also independent sets.

The first line contains two positive integers $n$ and $m$, representing the number of nodes and the number of paths. The next $n - 1$ lines each contain two positive integers $u_{i}$ and $v_{i}$, describing each edge of the tree. The next $m$ lines each contain two positive integers $a_{i}$ and $b_{i}$, describing each given path.

Output one positive integer, representing the final answer.

**Please pay attention to the impact of constant factors on the program's running time.** # Constraints For $10\%$ of the testdata: $1 \leq n \leq 10$, $1 \leq m \leq 10$. For $20\%$ of the testdata: $1 \leq n \leq 100$, $1 \leq m \leq 100$. For another $30\%$ of the testdata: $1 \leq m \leq 15$. For another $10\%$ of the testdata: $1 \leq n, m \leq 10^{5}$. For another $20\%$ of the testdata: $u_{i} = i, v_{i} = i + 1$. For $100\%$ of the testdata: $1 \leq n, m \leq 5 \times 10^{5}$. Translated by ChatGPT 5