P10064 [SNOI2024] Bus Routes

Given an unrooted tree with $n$ nodes. We want to build bus routes between some pairs of nodes so that between any two nodes, it takes at most two bus routes to travel. Formally, consider all $\frac{n (n - 1)}{2}$ simple paths on the tree whose endpoints are different. For a subset $S$ of these paths, we call it good if and only if: - Consider a new graph $G$. For a pair of nodes $u, v$, if and only if there exists a path $P$ in $S$ such that both $u$ and $v$ lie on $P$, we add an undirected edge of weight $1$ between $u$ and $v$. - Require that the distance between any two nodes in $G$ is at most $2$. You need to compute how many subsets $S$ are good. Since the answer may be large, output it modulo $998244353$.

The first line contains a positive integer $n$, the number of nodes. The next $n - 1$ lines each contain two positive integers $u, v$, representing a tree edge $(u, v)$.

Output one integer, the answer modulo $998244353$.

**[Sample \#1 Explanation]** For the first sample, all feasible plans are $\{(1, 3)\}, \{(1, 3), (1, 2)\}, \{(1, 3), (2, 3)\}, \{(1, 3), (1, 2), (2, 3)\}, \{(1, 2), (2, 3)\}$. --- **[Sample \#3]** See the attachments `bus/bus3.in` and `bus/bus3.ans`. This sample satisfies the constraints of testdata $11 \sim 14$. --- **[Sample \#4]** See the attachments `bus/bus4.in` and `bus/bus4.ans`. This sample satisfies the constraints of testdata $19 \sim 20$. --- **[Constraints]** For all testdata, it is guaranteed that $1 \le n \le 3000$. Details are as follows: | Testdata ID | $n \le$ | Special Property | |:-:|:-:|:-:| | $1 \sim 3$ | $6$ | None | | $4 \sim 7$ | $10$ | None | | $8 \sim 10$ | $3000$ | A | | $11 \sim 14$ | $100$ | None | | $15 \sim 18$ | $500$ | None | | $19 \sim 20$ | $3000$ | None | Special property A: the tree is a chain. Translated by ChatGPT 5