显然 \(k\) 为奇数时无解。
不妨转化为数列问题：构造一个有限数列 \(\{ a_{1}, a_{2}, \dots, a_{d} \}\)，数列需要满足以下条件：
-
\(a_{1} \le 1\)
-
\(a_{i} \le 2a_{i - 1}\)
-
\(w = \sum\limits_{1 \le i \le d}ia_{i} = \frac{k}{2}\)
数列 \(a\) 对应树的节点数为 \(1 + 2\sum\limits_{1 \le i \le d}a_{i}\)，数列 \(a\) 的字典序关系与深度序列的字典序关系一致。
为了最小化节点数，即最小化 \(s = \sum\limits_{1 \le i \le d}a_{i}\)，一个显然的思路是令所有 \(a_{i}\) 尽量等于 \(1\)，这样一来可以确定 \(d\) 的上界是 \(O(\sqrt{n})\) 级别的。
不妨设有一个全 \(1\) 数列，且其项数 \(d\) 满足 \(\sum\limits_{1 \le i \le d}i = \frac{d(d + 1)}{2} \le \frac{k}{2}\) 即 \(d(d + 1) \le k\)。
如果 \(d(d + 1) = k\)：该结构就是合法的最优解，直接输出即可。
否则，数列 \(a\) 必须进行一定的改动。比如，\(s \ge d + 1\)。
如果仍然在 \(d\) 项全 \(1\) 数列的基础上思考，并考虑如何让 \(a_{i} = 1\) 变成 \(a_{i} = x\)，那么问题会很棘手。
项数 \(d\) 不应该成为绊脚石，全 \(1\) 数列不应该成为绊脚石，毕竟它们不是答案的第一决定因素。
但这并不意味着先前的工作一无是处。比如，我们知道了 \(s \ge d + 1\)。
那就让 \(s\) 来主导思考的方向吧！
一个 \(s\) 值可以确定 \(w\) 的上下界：下界的情况就是把深度较浅的节点填满，上界的情况就是全 \(1\) 数列。为方便表示，记 \(V_{w}(s)\) 表示 \(s\) 所确定的 \(w\) 的取值集合。
我们可以肯定：\(K = \frac{k}{2}\) 小于 \(V_{w}(d + 1)\) 的上界。
那么下界如何呢？
- \(\inf{V_{w}(1)} = 1\)，\(\sup{V_{w}(1)} = 1\)
- \(\inf{V_{w}(2)} = 3\)，\(\sup{V_{w}(2)} = 3\)
- \(\inf{V_{w}(3)} = 5\)，\(\sup{V_{w}(3)} = 6\)
- \(\inf{V_{w}(4)} = 8\)，\(\sup{V_{w}(4)} = 10\)
- \(\inf{V_{w}(5)} = 11\)，\(\sup{V_{w}(5)} = 15\)
- \(s \ge 5\) 时：总有 \(\sup{V_{w}(s)} \ge \inf{V_{w}(s + 1)} - 1\)
即：除 \(K = 2, 4, 7\) 即 \(k = 4, 8, 14\) 外，\(K = \frac{k}{2}\) 一定介于 \(V_{w}(d + 1)\) 的上下界之间。
事情的发展开始变得清晰；我们很清楚我们希望看到怎样的结论：\(V_{w}(s)\) 是一段连续的值域。
正确性显然！从下界的情况出发，每次选取最大的 \(a_{i} > 1\)，令 \(a_{i + 1}\) 加一，\(a_{i}\) 减一。在到达上界之前，该操作总可以被执行，\(a\) 序列也总是合法，且 \(w\) 每次增加 \(1\)。
也就是说，\(s = d + 1\) 时一定有解！
于是我们证明了答案的存在性。
接下来，为了最小化序列字典序，我们希望深度较浅的节点数较少，即序列 \(a\) 中靠前的元素值较小。
假设我们已经确定了 \(a_{1} \sim a_{i - 1}\)，令 \(s^{'} = s - \sum\limits_{1 \le j < i}a_{j}\)，\(K^{'} = \frac{k}{2} - \sum\limits_{1 \le j < i}ja_{j}\)。
此时 \(s^{'}\) 当然也确定了 \(w^{'} = \sum\limits_{j \ge i}ja_{j}\) 的上下界，并且 \(w^{'}\) 值域连续，原理同上。我们假定在之前的构造过程中，保证进行到这一步时：\(s^{'}\) 可以确定出一段 \(w^{'}\) 的值域包含 \(K^{'}\)。初始条件即 \(s = d + 1, K = \frac{k}{2}\)，显然满足。
但是，\(s^{'}\) 具体（即考虑了 \(a_{i}\) 之后）决定了 \(w^{'}\) 的一段怎样的值域，还要取决于 \(a_{i}\) 的取值。
一个显然的性质是：\(w^{'}\) 的值域上下界均关于 \(a_{i}\) 单调不增。
如果 \(a_{i}\) 过小，\(K^{'}\) 可能小于 \(w^{'}\) 的下界；如果 \(a_{i}\) 过大，\(K^{'}\) 可能大于 \(w^{'}\) 的上界。
我们希望字典序尽量小，即 \(a_{i}\) 取一个使得 \(K^{'}\) 在 \(w^{'}\) 值域内的最小值即可；由于先前的限制，这样的 \(a_{i}\) 一定存在，且是以最优解存在。（所以我们不需要考虑上界；上界一定满足条件）
根据上述类似数学归纳法的算法流程，合法且字典序最小的序列被唯一确定。
时间复杂度 \(O(T\sqrt{k}\log{k})\)。