P15649 [NOI Qualifier Joint Contest 2026] Recollector

As time goes by, Xiao B returned to the NOI Qualifier arena that he had long dreamed of, yet once failed at. But how much does he still remember about competitive programming? And among those memories, which ones are the most precious and worth cherishing? Xiao B is passionate about competitive programming and loves exploring. To him, the most precious memories are probably the days when he learned algorithms by making all kinds of changes, running experiments, and trying to achieve something new. Xiao B wants you to accompany him to search for these precious memories. ---- 2026/3/13: Four groups of hack testdata were added.

You are given an undirected tree with $n$ nodes, numbered from $1$ to $n$. Define a heavy-light decomposition scheme as follows: - First, choose a node as the root, obtaining a rooted tree. - For every non-leaf node in the tree, choose **exactly one** child as its **heavy child**, and classify the edge connecting the node and its heavy child as a **heavy edge**; edges to its other children are **light edges**. - Then all heavy edges and their endpoints form several maximal simple paths. The nodes on each such path form a **heavy chain**. The **length** of a heavy chain is the number of nodes it contains. In particular, a node that is not incident to any heavy edge alone forms a heavy chain of length $1$. Xiao B recalls that when he learned heavy-light decomposition years ago, he proposed a **random chain decomposition** algorithm, with the following process: - First, set node $1$ as the root. - For each non-leaf node, choose its heavy child bottom-up: for a non-leaf node $u$ ($1 \le u \le n$), suppose it has $k$ children $v_1, v_2, \dots, v_k$. After the heavy child choices inside all child subtrees have been determined recursively, let the lengths of the heavy chains that contain $v_1, v_2, \dots, v_k$ be $l_1, l_2, \dots, l_k$, respectively. Then $u$ chooses proportionally to these lengths: the probability that $u$ chooses $v_i$ ($1 \le i \le k$) as the heavy child is $\frac{l_i}{\sum_{j=1}^{k} l_j}$. Xiao B knows that the time complexity of heavy-light decomposition is closely related to the number of **light edges** on the simple path from each node to the root. You need to help him compute, under the random chain decomposition algorithm above, for each node $x$ ($1 \le x \le n$), the **sum of expectations of the number of light edges** on the simple path from node $x$ to the root node $1$. Since the answer may be large, you only need to output it modulo $998244353$. The expectation is defined as follows: suppose a random variable $X$ can take values $x_1, \dots, x_m$, where $\Pr[X = x_i] = p_i \in [0,1]$ and $\sum_{i=1}^{m} p_i = 1$. Then the expectation of $X$ is $$ \mathbb{E}[X] = \sum_{i=1}^{m} p_i x_i. $$

**This problem contains multiple test cases.** The first line contains two non-negative integers $c, t$, representing the test point ID and the number of test cases. $c = 0$ means this test point is the sample. Then each test case is given as follows: - The first line contains a positive integer $n$, the number of nodes. - Line $i+1$ ($1 \le i \le n-1$) contains two positive integers $u_i, v_i$, denoting an edge between nodes $u_i$ and $v_i$.

For each test case, output one line with a non-negative integer: the sum, over all nodes, of the expected number of light edges on the simple path to the root, taken modulo $998244353$.

### Sample 1 Explanation. This sample contains two test cases. For the first test case: - Node $2$ chooses node $4$ or node $5$ as its heavy child with equal probability. - Node $1$ chooses node $2$ or node $3$ as its heavy child with probabilities $2/3$ and $1/3$, respectively. Therefore: - The expected number of light edges on the simple path from node $1$ to the root is $0$. - The expected number of light edges on the simple path from node $2$ to the root is $(2/3) \cdot 0 + (1/3) \cdot 1 = 1/3$. - The expected number of light edges on the simple path from node $3$ to the root is $(2/3) \cdot 1 + (1/3) \cdot 0 = 2/3$. - The expected number of light edges on the simple path from node $4$ to the root is $(2/3) \cdot (1/2) \cdot 0 + (2/3) \cdot (1/2) \cdot 1 + (1/3) \cdot (1/2) \cdot 1 + (1/3) \cdot (1/2) \cdot 2 = 5/6$. - The expected number of light edges on the simple path from node $5$ to the root is $5/6$. So the answer is $0 + 1/3 + 2/3 + 5/6 + 5/6 = 8/3 \equiv 665496238 \pmod{998244353}$. ### Sample 2. See `recollector/recollector2.in` and `recollector/recollector2.ans` in the contestant directory. This sample satisfies the constraints of test points $3 \sim 5$. ### Sample 3. See `recollector/recollector3.in` and `recollector/recollector3.ans` in the contestant directory. This sample satisfies the constraints of test points $6, 7$. ### Sample 4. See `recollector/recollector4.in` and `recollector/recollector4.ans` in the contestant directory. This sample satisfies the constraints of test points $8 \sim 10$. ### Sample 5. See `recollector/recollector5.in` and `recollector/recollector5.ans` in the contestant directory. This sample satisfies the constraints of test points $11, 12$. ### Sample 6. See `recollector/recollector6.in` and `recollector/recollector6.ans` in the contestant directory. This sample satisfies the constraints of test points $13 \sim 16$. ### Sample 7. See `recollector/recollector7.in` and `recollector/recollector7.ans` in the contestant directory. This sample satisfies the constraints of test points $17 \sim 25$. ### Constraints For all testdata: - $1 \le t \le 5$; - $1 \le n \le 5,000$; - For all $1 \le i \le n-1$, $1 \le u_i, v_i \le n$, and $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ form a tree. ::cute-table{tuack} | Test point ID | $n \le$ | Special property | |:-:|:-:|:-:| | $1, 2$ | $8$ | None | | $3 \sim 5$ | $20$ | ^ | | $6, 7$ | $500$ | A | | $8 \sim 10$ | ^ | None | | $11, 12$ | $1,500$ | B | | $13 \sim 16$ | ^ | None | | $17 \sim 25$ | $5,000$ | ^ | - Special property A: for all $1 \le i \le n-1$, $u_i = i$ and $v_i = i+1$. - Special property B: for all $1 \le x \le n$, the number of nodes on the simple path from node $1$ to node $x$ is at most $100$. Translated by ChatGPT 5