P14946 Bus Station

There is a tree with $n$ nodes. A subset $S$ of **all simple paths in the tree** is called good if and only if: - Every edge of the tree is covered by **exactly one** path in $S$. - Among all sets that satisfy the first condition, the maximum number of times any node appears as an endpoint of a path in $S$ is minimized. Count the number of good sets $S$. Output the answer modulo $998244353$.

Each test file contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2\cdot 10^4$), the number of test cases. For each test case: - The first line contains an integer $n$ ($2 \leq n \leq 10^5$), the number of nodes in the tree. - The next $n - 1$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq n$), indicating an edge between node $u$ and node $v$. It is guaranteed that all given edges form a tree. It is also guaranteed that, for a single test file, the sum of all $n$ does not exceed $2\cdot 10^5$.

For each test case, output one integer per line: the number of good sets $S$ modulo $998244353$.

For the first test case, the only possible $S$ that satisfy the first condition are $\{(1, 2), (2, 3)\}$ and $\{(1, 3)\}$. Since in $\{(1, 3)\}$ the maximum number of occurrences of any node as an endpoint is $1$, while in $\{(1, 2), (2, 3)\}$ it is $2$, only $\{(1, 3)\}$ is good. Translated by ChatGPT 5