#P13517. [2025年队测]圆形监狱
[2025年队测]圆形监狱
题目描述
给定一棵 个点的无根树 。对于在同样点集上的一棵 个点的无根树 ,不妨设有 条边同时出现在 与 中,则定义 的权值为 。
现在请你对于完全图的所有 棵生成树 求出其权值之和,对 取模。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,描述 上的一条边。
输出格式
输出一行,表示价值之和对 取模的结果。
样例输入 #1
4
1 2
2 3
3 4
样例输出 #1
94
样例解释 #1
的生成树有 种, 的生成树有 种, 的生成树有 种, 的生成树有 种。
数据范围/提示
本题共 个测试点,每个测试点等分。
| 测试点编号 | 特殊性质 | |
|---|---|---|
| 无 | ||
| A | ||
| B | ||
| 无 | ||
| A | ||
| B | ||
| A | ||
| B | ||
| 无 |
- 特殊性质 A:图是一条链。
- 特殊性质 B:图是一张菊花图。
请注意程序的输入输出效率,建议使用更快的 IO 实现方式。