P15649 [省选联考 2026] 找寻者 / recollector

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

给定一棵包含 $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$ 取模后的结果。

### 【样例 1 解释】 该样例共包含两组测试数据。对于第一组测试数据： - 结点 $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$。 故答案为 $0 + 1/3 + 2/3 + 5/6 + 5/6 = 8/3 \equiv 665496238 \pmod{998244353}$。 ### 【样例 2】 见选手目录下的 `recollector/recollector2.in` 与 `recollector/recollector2.ans`。 该样例满足测试点 $3 \sim 5$ 的约束条件。 ### 【样例 3】 见选手目录下的 `recollector/recollector3.in` 与 `recollector/recollector3.ans`。 该样例满足测试点 $6, 7$ 的约束条件。 ### 【样例 4】 见选手目录下的 `recollector/recollector4.in` 与 `recollector/recollector4.ans`。 该样例满足测试点 $8 \sim 10$ 的约束条件。 ### 【样例 5】 见选手目录下的 `recollector/recollector5.in` 与 `recollector/recollector5.ans`。 该样例满足测试点 $11, 12$ 的约束条件。 ### 【样例 6】 见选手目录下的 `recollector/recollector6.in` 与 `recollector/recollector6.ans`。 该样例满足测试点 $13 \sim 16$ 的约束条件。 ### 【样例 7】 见选手目录下的 `recollector/recollector7.in` 与 `recollector/recollector7.ans`。 该样例满足测试点 $17 \sim 25$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $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})$ 构成一棵树。 ::cute-table{tuack} | 测试点编号 | $n \le$ | 特殊性质 | |:-:|:-:|:-:| | $1, 2$ | $8$ | 无 | | $3 \sim 5$ | $20$ | ^ | | $6, 7$ | $500$ | A | | $8 \sim 10$ | ^ | 无 | | $11, 12$ | $1,500$ | B | | $13 \sim 16$ | ^ | 无 | | $17 \sim 25$ | $5,000$ | ^ | - 特殊性质 A：对于所有 $1\le i\le n-1$，均有 $u_i=i$ 且 $v_i=i+1$。 - 特殊性质 B：对于所有 $1\le x\le n$，结点 $1$ 到结点 $x$ 的简单路径所包含的结点数量均不超过 $100$。