recollector

题目背景

时过境迁，小 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$ 取模后的结果。

输入输出样例 #1

输入 #1

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

输出 #1

665496238
549034400

说明/提示

【样例 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$。

附加文件下载

recollector.zip