


这题显然是DP
首先,dp[i][j]表示树深度小于等于i,树的大小为j的有根树的数量$
可以循环枚举根节点编号次大的子树的大小k。
dp[i][j]=∑k=1j−1dp[i][j−k]∗dp[i−1][k]∗Cj−2k−1
注释:第一个dp表示的是除去这棵大小为k的子树的有根树数量,第二个dp表示的是这棵大小为k的子树的有根树数量,最后要给每一个点分配编号,只用分编号给(k的子树)或(除去k的剩余树),所以乘一个Cj−2k−1
因为一开始设的是深度小于等于i,所以最后要融斥去掉重复的树的数量。
因为一开始没有考虑这种树的好坏,所以当大小j是坏的时候,dp[i][j]=0。