logo AlgoBeat OnlineJudge
登录 注册

#102362. [BZOJ 2362] 二叉树计数

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

在那个植树节,晚上,小 L,小 H,小 X 讨论起了一个关于树的问题:

有多少个不同的二叉树最长链为

但是他们发现,答案随 增长的速度太快了,他们想不出什么好方法,便求助于你。

由于答案可能会很大,你只需要输出答案 后的结果即可。

输入格式

包含两个正整数 。表示询问有多少个不同的二叉树最长链为

输出格式

包含一个非负整数,为答案 后的结果。

样例输入

2 10

样例输出

7

数据范围与提示

关于二叉树:

二叉树的递归定义:二叉树要么为空,要么由根结点,左子树,右子树组成。左子树和右子树分别是一棵二叉树。

请注意,有根树和二叉树的三个主要差别:

  1. 树的结点个数至少为 ,而二叉树的结点个数可以为

  2. 树中结点的最大儿子个数没有限制,而二叉树结点的最大儿子个数为

  3. 树的结点无左、右之分,而二叉树的结点有左、右之分。

关于最长链:

最长链为这棵二叉树中一条最长的简单路径,即不经过重复结点的一条路径。可以容易证明,二叉树中最长链的起始、结束结点均为叶子结点。

对于 的数据,有