#P18923. [2026多校联测]杨桃超新星

[2026多校联测]杨桃超新星

杨桃超新星 (starfruit)

题目背景

题目背景

题目描述

抬头仰望星空,你发现星星之间的连线是有规律的,具体的说:

夜空中有 nn 颗星星,他们之间有 n−1n-1 条树边,连通成一整张图。

并且从左往右的每个相邻叶子节点(度数为 11,保证根节点度数不为 11)都有一条非树边。

星星时隐时现,他们间的连边也有 12\frac{1}{2} 的概率黯淡,你珍稀那些没有黯淡的边,你想要求出没有黯淡的边组成的连通块数量。

可这只是一厢情愿,你并不知道哪条边会黯淡,你能做的,只有思考每种情况,因此请你求出在每条边有 12\frac{1}{2} 的概率黯淡的情况下,没有黯淡的边组成的连通块数量期望,对 998244353998244353 取模。

输入格式

本题有多组测试数据,第一行输入一个正整数 TT 表示测试组数。

每组测试数据输入格式如下:

第一行输入一个整数 nn,表示节点数。

接下来 nn 行,每行输入一个 cic_i 表示儿子个数,接下来有 cic_i 个数,表示从左往右的儿子。

输出格式

每个测试数据输出一行一个整数,表示答案。

输入输出样例

样例一

输入
2
3
2 2 3
0
0
6
3 6 2 3
2 4 5
0
0
0
0
输出
374341634
694091779
解释

对于第一组测试数据,连边是:

(1,2)  (1,3)  (2,3)(1, 2) \ \ (1, 3) \ \ (2,3)

可以证明期望为 138\frac{13}{8}。

对于第二组测试数据,连边是:

$$(1,6) \ \ (1, 2) \ \ (1, 3) \ \ (2, 4) \ \ (2, 5) \ \ (6, 4) \ \ (4, 5) \ \ (5, 3)$$

可以证明期望为 295128\frac{295}{128}。

数据范围

本题采用子任务捆绑,只有通过子任务中的全部测试点才可获得分数。

本题有极大的子任务依赖。

子任务编号 nn 特殊性质 分数
11 1010 无 1010
22 1515 叶子数量不超过 66 2020
33 100100 无 1010
44 3×1033 \times 10^3 2020
55 3×1043 \times 10 ^ 4 叶子数量不超过 1010
66 3×1053 \times 10 ^ 5 树是一个菊花图 1010
77 无

对于全部测试数据 T≤10T \le 10。