Background

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.

Problem Description

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

Input Format

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$.

Output Format

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$.

0 2
5
1 2
1 3
2 4
2 5
8
1 2
1 3
2 4
2 5
2 6
5 7
3 8

665496238
549034400

Hint

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}

• 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