#P17714. [2026年江苏省队集训]粒子发生器
[2026年江苏省队集训]粒子发生器
题目描述
小Z获得了一个粒子发生器!
粒子发生器一次可以制造 个粒子,编号为 。每个粒子会被赋予一个能级,所有粒子的能级恰好构成 到 的一个排列——也就是说,每个整数恰好出现一次。能级的数值越小,代表粒子的能量越低,状态越稳定。
粒子之间存在着相互作用,这些相互作用构成了一棵树:如果两个粒子之间有边,则它们可以直接交换能量。小Z发现,如果一个粒子的能级严格小于它所有邻居的能级,那么这个粒子就会处于基态——它是局部区域中最稳定的存在。
现在,小Z想知道:对于每个可能的 ,有多少种不同的能级分配方案,使得恰好有 个粒子处于基态?
由于答案可能非常巨大,你只需输出对 取模后的结果。小Z百思不得其解,请你帮他计算一下吧!
输入格式
第一行一个整数 。
接下来 行,每行两个整数 ,表示粒子 和粒子 之间存在相互作用。
输出格式
共 行,每行一个整数。第 行的整数表示 时的方案数模 的结果。
样例1输入
3
1 2
1 3
样例1输出
4
2
0
样例1解释:
粒子1处在基态的方案有 。
粒子2处在基态的方案有 。
粒子3处在基态的方案有 。
粒子2,3处在基态的方案有 。
其余情况不会出现。
样例2输入
5
1 2
1 3
2 4
2 5
样例2输出
28
54
38
0
0
数据范围
对于所有测试数据, 且保证输入的图是一棵树。
| 子任务编号 | 分值 | n | 图形态 |
|---|---|---|---|
| 1 | 10 | 树 | |
| 2 | 5 | ||
| 3 | 10 | 菊花 | |
| 4 | 5 | 链 | |
| 5 | |||
| 6 | 10 | ||
| 7 | 15 | 树 | |
| 8 | 10 | ||
| 9 | |||
| 10 | 20 |