F 小红的树构造

题意：小红定义一颗树是好树，当且仅当对于所有非叶子节点，它们度数的最大公因数恰好为 。请你构造一颗包含 个节点的好树。

要求度数相关，我们知道，一个 个节点的树，会有 的度数。题目要求所有非叶子节点的度数的最大公因数恰好为 ，我们把这些非叶子节点都拿出来，记它们的度数为 。我们需要满足下面的性质：

除此以外，我们还知道：

综合上述两条性质，我们知道 ，都有 ，所以有：

我们现在考虑把 的方案构造出来，然后再通过 的构造将树的构造推导出来。

我们现在令一「捆」为 个数，记每个位置的「捆」数为 ，我们现在只需要让 即可。

关于 ，我们有一个显然的构造：

我们还需要保证：

解得 ，我们只要找到一个 直接按上述构造即可。如果找不到满足条件的 ，显然是无解的，因为没有足够的点可以满足所有点都有至少一「捆」的数。

但是我们并没有做完，你会发现，非叶子节点 ，所以当 时，无法构造出来形似 的形式。我们接下来讨论 时如何构造。

当 时，我们考虑用两个质数 来构造，同时直接令 ，构造的 为：

当 时，令 ，保留上面数组的前两位即可。

当 时，手玩几组数据，容易知道，这是无解的。

知道 后，将其还原为 ，通过 来构造一课树。

  • 首先将所有非叶子节点连成一条链。
  • 从第一个点开始依次给每个点接叶子即可。

我们只需要证明，对于非叶子节点度数的序列 ，如果 ，且 ，那么刚刚的构造一定是合法的。

  • 证：我们只需要满足两个限制：第一个限制，接的叶子节点的个数是等于 的；第二个限制，每个非叶子节点的度数恰好等于 。
  • 我们给第一个点和最后一个点接 个叶子，给其他点接 个叶子，这里我们只讨论 的情况， 的情况是容易的。
  • 对于第一个限制，我们一共接了 个叶子，化简得到，处理的叶子总数为 ，这与我们预期的叶子总数是一致的；
  • 对于第二个限制，由于我们将相邻的非叶子节点相连了，所以除了头和尾，每个节点的度数为 ，对于头和尾，它们的度数为 ，都满足我们的条件。

所以我们的构造一定是合法的。

另外的结论

我们已经保证了 ，我们可以证明其他所有的情况都可以通过这个构造到达。

  • 若在某种情况里，存在一个非叶子节点 连接了大于等于 个非叶子节点，我们可以在这些点中任取一个点，并且保证它只跟两个非叶子节点相连（如果没有，进入任意一个节点的子树，递归下去），并将它接在 与其他的某个非叶子节点之间，并把跟它相连的另一个节点接在 上，此时，所有非叶子节点的度数都没有变化，每次都能将某一个分支剪掉，
  • 不停的做下去，直到它变成「一条链」。

我们只需要把上述操作倒着做一遍就能到达原先的状态。