4333. [省选联考 2026] 找寻者

【题目背景】

时过境迁，小 B 回到了他梦寐以求，却又折戟沉沙的省选赛场。但他关于算法竞赛的记忆还有多少呢？其中又有多少最为珍贵的记忆值得去珍惜呢？小 B 是一个对算法竞赛充满热情，乐于探索的人。而对他来说，最珍贵的记忆便是学习算法时对其进行各种修改、实验，尝试得到一些新成果的日子吧。
小 B 想请你陪他一起，去找寻这些珍贵的记忆。

【题目描述】

给定一棵包含 $n$ 个结点的无根树，结点的编号为 $1 \sim n$。
定义一种轻重链剖分方案如下：

• 首先指定某个结点作为树根，得到一棵有根树；
• 对于树上的每个非叶结点，选择恰好一个儿子作为重儿子，并将连接该结点与重儿子的边划分为重边，与其他儿子的连边划分为轻边；
• 此时，树上的所有重边及其端点构成了若干条极长简单路径，每条路径上的所有结点构成一条重链。定义一条重链的长度为其包含的结点数量。特别地，未与任何重边相连的结点单独构成一条长度为 $1$ 的重链。

小 B 回想起，多年前在学习轻重链剖分时，他曾提出过一种随机链剖分的算法，具体流程如下：

• 首先指定结点 $1$ 作为树根；
• 对树上的每个非叶结点自底向上地选择重儿子：对于非叶结点 $u$ ($1 \le u \le n$)，设其有 $k$ 个儿子 $v_1, v_2, \dots, v_k$。在递归确定出所有儿子的重儿子后，设 $v_1, v_2, \dots, v_k$ 各自所在的重链的长度分别为 $l_1, l_2, \dots, l_k$。则 $u$ 会以正比于重链长度的概率进行选择，即选择 $v_i$ ($1 \le i \le k$) 作为重儿子的概率为 $\frac{l_i}{\sum_{j=1}^{k} l_j}$。

小 B 知道，轻重链剖分的时间复杂度与各个结点到根结点的简单路径所包含的轻边数量密切相关。你需要帮助他求出，在上述随机链剖分算法下，对于每一个结点 $x$ ($1 \le x \le n$)，从结点 $x$ 到根结点 $1$ 的简单路径所包含的轻边数量的期望之和。由于答案可能较大，你只需求出其对 $998244353$ 取模后的结果。
期望的定义如下：设随机变量 $X$ 所有可能的取值分别为 $x_1, \dots, x_m$，其中 $X = x_i$ ($1 \le i \le m$) 的概率为 $p_i \in [0,1]$，且 $\sum_{i=1}^{m} p_i = 1$，则 $X$ 的期望为 $$ \mathbb{E}[X] = \sum_{i=1}^{m} p_i x_i. $$

【输入格式】

本题包含多组测试数据。
输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。
接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$，表示结点的数量。
• 第 $i+1$ ($1 \le i \le n-1$) 行包含两个正整数 $u_i, v_i$，表示连接结点 $u_i$ 与结点 $v_i$ 的一条树边。

【输出格式】

对于每组测试数据，输出一行一个非负整数，表示所有结点到根结点的简单路径所包含的轻边数量的期望之和对 $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

【样例说明】

该样例共包含两组测试数据。对于第一组测试数据：

• 结点 $2$ 将以均等的概率选择结点 $4$ 与结点 $5$ 作为重儿子；
• 结点 $1$ 将分别以 $2/3, 1/3$ 的概率选择结点 $2, 3$ 作为重儿子。

• 结点 $1$ 到根结点的简单路径所包含的轻边数量的期望为 $0$；
• 结点 $2$ 到根结点的简单路径所包含的轻边数量的期望为 $(2/3) \cdot 0 + (1/3) \cdot 1 = 1/3$；
• 结点 $3$ 到根结点的简单路径所包含的轻边数量的期望为 $(2/3) \cdot 1 + (1/3) \cdot 0 = 2/3$；
• 结点 $4$ 到根结点的简单路径所包含的轻边数量的期望为 $(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$；
• 结点 $5$ 到根结点的简单路径所包含的轻边数量的期望为 $5/6$。

【数据规模与约定】

对于所有测试数据，均有：

• $1 \le t \le 5$；
• $1 \le n \le 5,000$；
• 对于所有 $1 \le i \le n-1$，均有 $1 \le u_i, v_i \le n$，且 $(u_1, v_1), \dots, (u_{n-1}, v_{n-1})$ 构成一棵树。

【来源】

省选联考 2026 Day1 T1

样例下载