为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/nocows
目录 |
[编辑] 分析
（官方题解， 译 by 巨菜逆铭）
这是一个DP问题。我们所关心的树的性质是深度和节点数，所以我们可以做这样一张表：table[i][j]表示深度为i、节点数为j的树的个数。根据给定的约束条件，j必须为奇数。你如何构造一棵树呢？当然是由更小的树来构造了。一棵深度为i、节点数为j的树可以由两个子树以及一个根结点构造而成。当i、j已经选定时，我们选择左子树的节点数k。这样我们也就知道了右子树的节点数，即j-k-1。至于深度，至少要有一棵子树的深度为i-1才能使构造出的新树深度为i。有三种可能的情况：左子树深度为i-1 ，右子树深度小于i-1；右子树深度为i-1，左子树深度小于i-1；左右子树深度都为i-1。事实上，当我们在构造一棵深度为i的树时，我们只关心使用的子树深度是否为i-1或更小。因此，我们使用另一个数组smalltrees[i-2][j]记录所有深度小于i-1的树，而不仅仅是深度为i-2的树。知道了上面的这些，我们就可以用以下三种可能的方法来建树了：
table[i][j] := smalltrees[i-2][k]*table[i-1][j-1-k];
// 左子树深度小于i-1，右子树深度为i-1
table[i][j] := table[i-1][k]*smalltrees[i-2][j-1-k];
// 左子树深度为i-1，右子树深度小于i-1
table[i][j] := table[i-1][k]*table[i-1][j-1-k];
// 左右子树深度都为i-1 另外，如果左子树更小，我们可以对它进行两次计数，因为可以通过交换左右子树来得到不同的树。总运行时间为O(K*N^2)，且有不错的常数因子。（官方标程见源码-c部分）
[编辑] 另一种思路
首先明确一下题目的意思：用N个点组成一棵深度为i的二叉树，求一共有几种方法？ 设dp[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则：
dp[i,j]=∑(dp[k,j-1]×dp[i-1-k,j-1])(k in {1..i-2})
边界条件：dp[1,i]=1
我们要求的是深度恰好为K的方法数S，易知S=dp[n,k]-dp[n,k-1]。 但需要注意的是，如果每次都取模，最后可能会有dp[n,k]<dp[n,k-1],所以可以用S=(dp[n,k]-dp[n,k-1]+v) mod v
给出n,k,求满足以下条件的二叉树个数 1.每个结点的度为偶数 2.该树有n个结点 3.该树的深度为k 问题分析: 用动态规划和乘法原理求解,可以观察到一个树G(有x个结点,深度为k),如果去除它的根结点可以得到两个子数G1,G2,这两个子图的深度为k-1,他们的结点数的和为x-1.设其中G1有i个结点则G2有x-1-i个结点.
定义P(G)为与满足条件的二叉树G有同样多结点有深度相同且同样满足条件的树的个数.
将二叉树按上述方法依次分解为(有1个结点,深度为k-1的树和有x-1-1个结点深度为k-1的树),(有2个结点,深度为k-1的树和有x-1-2个结点深度为k-1的树),(有3个结点,深度为k-1的树和有x-1-3个结点深度为k-1的树)...(有x-1-1个结点,深度为k-1的树和有1个结点深度为k-1的树)...
由乘法原理得到:由G按上述方法分解成的每对二叉树(Gx,Gy)加一个根结点构成的二叉树的个数有P(Gx)*P(Gy)个.
G可以分解为x-2对子树,由加法原理得到P(G)=∑P(Gi)*P(Gj){(i,j)∈G可以分解到的子树对(Gi,Gj)}
定义f(x,k)满足为深度为k,结点个数为x,每个结点的度为偶数的二叉树的个数,由上述分析得到f(x,k)=∑(f(x-1-i,k-1)*f(i,k-1){1<=i<=x-2}.
[编辑] 再一种貌似不知对不对的思路
设 f[i][j]表示 前i个点组成的小于等于k高度的满足题意的个数 这样高度要求是小于k的就直接引用 高度要求一定等于k的就是f[i][k]-f[i][k-1] 即表示差量部分 转移方程差不多就那样f[i][k]-f[i][k-1]=(f[p][k-1]-f[p][k-2])*f[i-1-p][k-1]+(f[i-1-p][k-1]-f[i-1-p][k-2])*f[p][k-1]; 再把左边移项到右边就行了 p为左边节点数 （？p==i-p-1的时候,这个会不会加多）
[编辑] 有一种很奇怪没有试过的思路
可不可以这样呢？首先画一棵深度为K的满二叉树，然后从最后一层开始慢慢删除节点，删除2^k-1-n个节点时，就是一种家谱。
