物种关系树
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
背景
小明瞎看 OI-WIKI,看出来了下一个 T2。
题目描述
小明最近喜欢研究生物,尤其是物种之间的基因关系。
比如, 猴子跟猩猩有直接的亲戚关系,猩猩跟猿有直接的亲戚关系,人和猿有直接的亲戚关系,那么就有这样四条边,我们可以认为人跟猴子之间的基因距离是 ,因为这中间一共经历了 个物种。
现在,生物教练徐老师提出了这样一个问题:
假设有 个物种,他们构成了一棵 个节点的有根树,其中:
(1)节点无标号顺序,也就是所有节点都是不可区分的。
(2)所有子树是有顺序的,也就是,如果一个点先接了子树 ,再接了子树 ,跟先接了子树 ,再接了子树 是有区别的。 (3)这棵树上最远的基因距离不超过 ,也就是,任意两个节点之间的路径上,最多只有 个点。
问:这样的树有多少种。
具体的解释请看第一组样例。
输入格式
第一行输入 。
输出格式
输出一个数字表示答案 。
样例输入 #1
4 4
样例输出 #1
5
样例解释 #1
由于跟距离没啥关系了,所以一共有 种满足要求的树。

样例输入 #2
5 4
样例输出 #2
10
样例解释 #2
一共有 种满足要求的树:

样例输入 #3
80 80
样例输出 #3
381008905
样例输入 #4
80 50
样例输出 #4
164540686
样例输入 #5
10 6
样例输出 #5
2750
数据范围
本题共 20 个测试点。
| 测试点编号 | ||
|---|---|---|
| 1 | =5 | |
| 2~5 | / | |
| 6~9 | ||
| 10~11 | ||
| 12~13 | ||
| 14~15 | / | |
| 16~20 | / | |
对于全部测试数据:。