#P18923. [2026多校联测]杨桃超新星
[2026多校联测]杨桃超新星
杨桃超新星 (starfruit)
题目背景

题目描述
抬头仰望星空,你发现星星之间的连线是有规律的,具体的说:
夜空中有 颗星星,他们之间有 条树边,连通成一整张图。
并且从左往右的每个相邻叶子节点(度数为 ,保证根节点度数不为 )都有一条非树边。
星星时隐时现,他们间的连边也有 的概率黯淡,你珍稀那些没有黯淡的边,你想要求出没有黯淡的边组成的连通块数量。
可这只是一厢情愿,你并不知道哪条边会黯淡,你能做的,只有思考每种情况,因此请你求出在每条边有 的概率黯淡的情况下,没有黯淡的边组成的连通块数量期望,对 取模。
输入格式
本题有多组测试数据,第一行输入一个正整数 表示测试组数。
每组测试数据输入格式如下:
第一行输入一个整数 ,表示节点数。
接下来 行,每行输入一个 表示儿子个数,接下来有 个数,表示从左往右的儿子。
输出格式
每个测试数据输出一行一个整数,表示答案。
输入输出样例
样例一
输入
2
3
2 2 3
0
0
6
3 6 2 3
2 4 5
0
0
0
0
输出
374341634
694091779
解释
对于第一组测试数据,连边是:
可以证明期望为 。
对于第二组测试数据,连边是:
$$(1,6) \ \ (1, 2) \ \ (1, 3) \ \ (2, 4) \ \ (2, 5) \ \ (6, 4) \ \ (4, 5) \ \ (5, 3)$$可以证明期望为 。
数据范围
本题采用子任务捆绑,只有通过子任务中的全部测试点才可获得分数。
本题有极大的子任务依赖。
| 子任务编号 | 特殊性质 | 分数 | |
|---|---|---|---|
| 无 | |||
| 叶子数量不超过 | |||
| 无 | |||
| 叶子数量不超过 | |||
| 树是一个菊花图 | |||
| 无 |
对于全部测试数据 。