#PQJ3493x17301. QOJ 3493_17301

    ID: 2928 传统题 1500ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十七省联合省选2026

QOJ 3493_17301

2026 联合省选 第一试找寻者(recollector) 找寻者(recollector) 【题目背景】 时过境迁,小B 回到了他梦寐以求,却又折戟沉沙的省选赛场。但他关于算法竞赛 的记忆还有多少呢?其中又有多少最为珍贵的记忆值得去珍惜呢?小B 是一个对算法 竞赛充满热情,乐于探索的人。而对他来说,最珍贵的记忆便是学习算法时对其进行各 种修改、实验,尝试得到一些新成果的日子吧。 小B 想请你陪他一起,去找寻这些珍贵的记忆。 【题目描述】 给定一棵包含n 个结点的无根树,结点的编号为1 ∼n。 定义一种轻重链剖分方案如下: • 首先指定某个结点作为树根,得到一棵有根树; • 对于树上的每个非叶结点,选择.恰.好一个儿子作为.重.儿.子,并将连接该结点与重 儿子的边划分为.重.边,与其他儿子的连边划分为.轻.边; • 此时,树上的所有重边及其端点构成了若干条极长简单路径,每条路径上的所有 结点构成一条.重.链。定义一条重链的.长.度为其包含的结点数量。特别地,未与任 何重边相连的结点单独构成一条长度为1 的重链。 小B 回想起,多年前在学习轻重链剖分时,他曾提出过一种.随.机链剖分的算法,具 体流程如下: • 首先指定结点1 作为树根; • 对树上的每个非叶结点自底向上地选择重儿子:对于非叶结点u (1 ≤u ≤n),设 其有k 个儿子v1, v2, . . . , vk。在递归确定出所有儿子的重儿子后,设v1, v2, . . . , vk 各自所在的重链的长度分别为l1, l2, . . . , lk。则u 会以.正.比.于重链长度的概率进 行选择,即选择vi (1 ≤i ≤k) 作为重儿子的概率为 li !k j=1 lj 。 小B 知道,轻重链剖分的时间复杂度与各个结点到根结点的简单路径所包含的 .轻.边数量密切相关。你需要帮助他求出,在上述随机链剖分算法下,对于每一个结点 x (1 ≤x ≤n),从结点x 到根结点1 的简单路径所包含的.轻.边数量的.期.望之和。由于答 案可能较大,你只需求出其对998, 244, 353 取模后的结果。 .期.望的定义如下:设随机变量X 所有可能的取值分别为x1, . . . , xm,其中X = xi (1 ≤i ≤m) 的概率为pi ∈[0, 1],且!m i=1 pi = 1,则X 的.期.望为 E[X] = m " i=1 pixi. 【输入格式】 从文件recollector.in 中读入数据。 第2 页 共13 页

2026 联合省选 第一试找寻者(recollector) .本.题.包.含.多.组.测.试.数.据。 输入的第一行包含两个非负整数c, t,分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。 接下来依次输入每组测试数据,对于每组测试数据: • 第一行包含一个正整数n,表示结点的数量。 • 第i + 1 (1 ≤i ≤n −1) 行包含两个正整数ui, vi,表示连接结点ui 与结点vi 的 一条树边。 【输出格式】 输出到文件recollector.out 中。 对于每组测试数据,输出一行一个非负整数,表示所有结点到根结点的简单路径所 包含的轻边数量的期望之和对998, 244, 353 取模后的结果。 【样例1 输入】 1 0 2 2 5 3 1 2 4 1 3 5 2 4 6 2 5 7 8 8 1 2 9 1 3 10 2 4 11 2 5 12 2 6 13 5 7 14 3 8 【样例1 输出】 1 665496238 2 549034400 第3 页 共13 页

2026 联合省选 第一试找寻者(recollector) 【样例1 解释】 该样例共包含两组测试数据。对于第一组测试数据: • 结点2 将以均等的概率选择结点4 与结点5 作为重儿子; • 结点1 将分别以2/3, 1/3 的概率选择结点2, 3 作为重儿子。 因此, • 结点1 到根结点的简单路径所包含的轻边数量的期望为0; • 结点2 到根结点的简单路径所包含的轻边数量的期望为(2/3)·0+(1/3)·1 = 1/3; • 结点3 到根结点的简单路径所包含的轻边数量的期望为(2/3)·1+(1/3)·0 = 2/3; • 结点4 到根结点的简单路径所包含的轻边数量的期望为(2/3) · (1/2) · 0 + (2/3) · (1/2) · 1 + (1/3) · (1/2) · 1 + (1/3) · (1/2) · 2 = 5/6; • 结点5 到根结点的简单路径所包含的轻边数量的期望为5/6。 故答案为0 + 1/3 + 2/3 + 5/6 + 5/6 = 8/3 ≡665, 496, 238 (mod 998, 244, 353)。 【样例2】 见选手目录下的recollector/recollector2.in 与recollector/recollector2.ans。 该样例满足测试点3 ∼5 的约束条件。 【样例3】 见选手目录下的recollector/recollector3.in 与recollector/recollector3.ans。 该样例满足测试点6, 7 的约束条件。 【样例4】 见选手目录下的recollector/recollector4.in 与recollector/recollector4.ans。 该样例满足测试点8 ∼10 的约束条件。 【样例5】 见选手目录下的recollector/recollector5.in 与recollector/recollector5.ans。 该样例满足测试点11, 12 的约束条件。 【样例6】 见选手目录下的recollector/recollector6.in 与recollector/recollector6.ans。 该样例满足测试点13 ∼16 的约束条件。 第4 页 共13 页

2026 联合省选 第一试找寻者(recollector) 【样例7】 见选手目录下的recollector/recollector7.in 与recollector/recollector7.ans。 该样例满足测试点17 ∼25 的约束条件。 【数据范围】 对于所有测试数据,均有: • 1 ≤t ≤5; • 1 ≤n ≤5, 000; • 对于所有1 ≤i ≤n −1,均有1 ≤ui, vi ≤n,且(u1, v1), . . . , (un−1, vn−1) 构成一 棵树。 测试点编号 n ≤ 特殊性质 1, 2 8 无 3 ∼5 20 6, 7 500 A 8 ∼10 无 11, 12 1, 500 B 13 ∼16 无 17 ∼25 5, 000 特殊性质A:对于所有1 ≤i ≤n −1,均有ui = i 且vi = i + 1。 特殊性质B:对于所有1 ≤x ≤n,结点1 到结点x 的简单路径所包含的结点数量 均不超过100。 第5 页 共13 页