HatRack
作者：毛啸
关键词：完全二叉树 树形DP
题目简述
给定一棵个点的不带标号的树，判断有多少种标号方式满足对于编号为的点，对于编号为的点以及编号为的点，如果它存在，那么就与编号为的点有一条边相连。换句话说就是形成一棵完全二叉树。
。
宽松的限制
我们注意到的范围很小，这就意味着一般的多项式时间复杂度都是可以接受的。
所以，我们不妨枚举一些东西来简化问题。一种常见的方法就是枚举编号为的点也就是根是哪一个。
可行性
我们要做的第一件事情，就是判断枚举根之后的问题是否有解——这也是必需的，因为我们要求的是标号方案数，而是否有解是判断方案数是否为零，显然这是一个子问题。
那么怎么判断呢，我们考虑完全二叉树的性质。
直接用题目简述中的定义？我们连标号都不知道，如果将标号设为状态去DP又难想又不一定好写。
用完全二叉树给我们的形状上感觉，通俗的来说也就是非最下面是满的，最下面是左边才有节点？还是一样，你连标号都不知道，当然我们的确可以用度数判断出来哪些是最下面，但你又怎么知道最下面的点的顺序？
所以怎么办呢？考虑我们现在知道什么？我们知道树的形态却不知道标号，因此我们应该避免用到和标号有关的性质？那么有什么性质呢？我们已经知道根了，所以孩子个数以及深度都是可以确定的，我们应该从这些方面下手。
首先如果孩子个数大于2，显然就不可行了。
然后，完全二叉树是基本平衡的，所以我们发现一个点下面的最大深度减去最小深度一定不会超过1。
显然孩子个数随便求，最大最小深度也可以用简单的树形DP解决。
仅仅这样就够了吗？我们考虑一条长度为5的链，这显然是没有合法标号的，然而假如我们把中间的点做根，会发现他满足上面两个条件！
怎么修补呢？我们发现，我们还少考虑了一种情况——对于每一个深度，最大深度不等于最小深度的点不能多于一个。
经过这个修补，我们的算法终于完美了，也就是说我们学会了判可行性。
统计方案数
那么接下来我们要做的事情，就是统计方案数了。
这个方案数怎么统计呢，我们发现，对于某一个节点，如果它的孩子数是两个，并且最大深度等于最小深度，那么它对应的子树就是一棵满二叉树。
我们很容易发现，对于一个方案，所有满足上述条件的点，你都可以通过交换两棵子树得到一个新的方案。
相反，如果不满足上述条件，显然交换两棵子树之后不合法。
这也就意味着，假设有个满足上述条件的点，方案数就是，因为每个节点都可以交换或者不交换。
那么我们就完美的解决了这个问题。由于要枚举个根，每次需要遍历一遍整棵树，所以总的时间复杂度是，空间复杂度。
优化
如果你是一个完美主义者，显然不会满足于这一步，那么本题还能怎么优化呢？
其实很简单，容易发现一个完全二叉树最多只有两个点度数（注意不是孩子数）为二，其中一个必然是根，所以，根的枚举范围变为，时间复杂度降为。
总结
本题的解决过程看起来十分顺利，这都是因为一个好的思考方式——化整为零，我们正是通过逐步简化问题，不断考虑问题的子问题，最终才能解决整个题目的，比如，我们通过可行性的判断，引出了记录最大深度和最小深度的思想，从而直接实现了从零到全部的飞跃。