对于树
对于两棵树
称
问:
给定
棵 个点的树 ,求满足 的有标号树 构成的等价类数量。给定
棵 个点的树 ,求满足 的有标号树 数量。
注意两问的计数对象不同。两问答案均对
保证答案取模后非
输入格式
从标准输入读入数据。
输入第一行一个整数
接下来一行两个正整数
接下来依次输入
输出格式
输出到标准输出。
输出一行一个整数表示答案对
样例 #1
样例输入 #1
0 1 4 1 2 1 3 1 4
样例输出 #1
2
【样例 1 解释】
可以证明
可以验证链对应的等价类和该树本身所在的等价类均满足要求,而其他等价类不满足要求。
样例 #2
样例输入 #2
1 1 4 1 2 2 3 3 4
样例输出 #2
16
【样例 2 解释】
可以验证所有
【样例 3 ~ 10】
见题目目录下的 3.in
~ 10.in
与 3.ans
~ 10.ans
。
子任务
对于所有数据,保证
子任务编号 | 树形态 | 分数 | |||
---|---|---|---|---|---|
无特殊形态 | |||||
菊花 | |||||
无特殊形态 | |||||
无特殊形态 | |||||
无特殊形态 | |||||
无特殊形态 | |||||
链 | |||||
无特殊形态 | |||||
无特殊形态 | |||||
无特殊形态 | |||||
无特殊形态 |
“树形态”中,“菊花”指存在一个向所有点有直接连边的点,“链”指所有点度数不超过