标算只能做到 $C = 44$，人类做到了 $C = 38$？玩得也太差了！可以把最坏情况降到 $C\le28$，而且是确定性方案，不依赖随机哈希，也不要求同值兄弟保持固定的访问顺序。

核心改进有两个：用一条长链的前两个节点共同编码身份，让每轮恢复长链的数量变成两个值域大小的乘积；把剩余单点叶子的识别转化为子集计数，不再要求每轮给每片叶子分配不同的值。

下面给出完整构造、正确性证明、最坏上界的有限参数验证，以及实现。题目的限制是 $N\le1000$、$M\le200$，优化目标为 $C=K+B$，其中 $B$ 是所有 insert 调用使用过的最大值，所以实际有 $B+1$ 种可用颜色。

一、先把树分解成链

依次处理叶子 $0,1,\ldots,M-1$。对于叶子 $i$，不断调用 insert(i,...)，直到返回 false，记成功次数为 $\ell_i$。

这些新放入的球一定构成一条自上而下的链，最后一个节点就是叶子 $i$。所有链两两不交，覆盖整棵树，因此 $N=\sum_i\ell_i$。除了包含根的第 $0$ 条链，其余每条链的链头都挂在更早的某条链上。

称 $\ell_i\ge2$ 的链为长链，$\ell_i=1$ 的链为单点叶子。一个重要性质是：

所有内部节点都属于长链。只要恢复所有长链，就已经知道完整的内部骨架，剩下的只是若干叶子的父亲。

第一次填球时，我们顺便恢复一个初始子树。

当 $M\le8$ 时，给第 $i$ 条链全部使用颜色 $M-1-i$，一次 collect 就能恢复整棵树，此时 $C=M\le8$。

以下考虑 $M>8$。给前 $8$ 条链分别使用颜色 $8,7,\ldots,1$，其余链全部使用颜色 $0$。填满后调用一次 collect，删除返回序列中的所有 $0$，剩下的就是前 $8$ 条链组成的子树的先序遍历。

为什么可以直接恢复？因为后加入的链颜色更小，所以挂在某条链上的其他链，总会先于该链的下一个节点被遍历。维护一个栈，每种颜色第一次出现时开始一条链，出现满 $\ell_i$ 次时结束这条链即可。

记长链总数为 $D$，前 $8$ 条链中的长链数量为 $a$。此时已经知道 $a$ 条长链和 $8-a$ 个单点叶子，还需要定位的单点叶子数量为 $s=M-D-8+a$。

接下来始终按照原来的叶子顺序加入剩余长链；单点叶子暂时跳过。跳过它们不会改变任何长链的落球位置，因为它们不包含内部节点。

二、用两个节点编码一条长链

这一部分先解决一个基础问题：如何用很小的值域，在返回序列中认出已经知道的内部节点？

假设已经恢复了 $d$ 条长链。保留全部已知内部节点，但在本轮填球时，对已知叶子进行如下删减：一个内部节点如果有内部孩子，就不填它的叶子孩子；否则只保留一个叶子孩子。

这样得到的辅助树具有一个方便的性质：每个内部节点，要么所有孩子都是内部节点，要么只有一个叶子孩子。辅助树的叶子数不超过 $d$，因为每个最底层内部节点必然是某条已恢复长链的最后一个内部节点。

取 $b$ 满足 $b^2\ge d$。我们要用颜色 $0,\ldots,b-1$，使任意兄弟内部节点 $v$ 的二元组 $(c(v),\min_{w\text{ 是 }v\text{ 的孩子}}c(w))$ 两两不同。

这个性质意味着：看到某个内部节点的颜色，再看到它第一个旧孩子的颜色，就能知道它是哪一个节点。即使同值兄弟任意换序，也没有影响；题目确实允许这样的换序，不能假设它们的顺序稳定。

颜色的具体构造如下。

自底向上处理。只有一个叶子孩子的内部节点，令这个叶子的颜色为 $0$。

对于其余内部节点 $u$，先递归处理所有孩子。设孩子 $v$ 的孩子们目前共有 $d_v$ 种不同颜色。将长度分别为 $d_v$ 的区间依次铺在从 $0$ 开始的整数轴上；设分给 $v$ 的区间是 $[L_v,R_v]$。

令 $c(v)=\lfloor R_v/b\rfloor$，并把 $v$ 的孩子们原来的颜色等价类，依次重命名为 $L_v\bmod b,(L_v+1)\bmod b,\ldots,R_v\bmod b$。

这个操作合法且满足要求：

设 $v$ 的子树有 $L$ 个辅助树叶子，归纳可得 $d_v\le\lceil L/b\rceil\le b$。同时，一个节点的所有孩子对应的 $d_v$ 之和不超过其子树叶子数，因而不超过 $b^2$，所以产生的所有颜色都在 $0,\ldots,b-1$ 内。

对于颜色相同的兄弟节点，它们的区间右端点位于同一个长度为 $b$ 的区间中。由于每段长度不超过 $b$，至多第一段跨越取模边界；其余段取模后的起点严格递增。因此，它们孩子颜色的最小值两两不同。

此外，对颜色等价类进行双射重命名，不会破坏子树中已经建立的二元组唯一性。

辅助树结构已知，填球也很简单：给每个节点预先选择一个保留的后代叶子，按先序遍历顺序向该叶子插球。因为祖先已经占满，球恰好停在当前节点。

现在开始批量加入新长链。

固定本次方案的最大值 $B$，选择 $b\ge\lceil\sqrt d\rceil$，令 $h=B+1-b$。

把旧辅助树的颜色整体加上 $h$，于是旧节点使用 $h,\ldots,B$。对于本批第 $j$ 条新长链，使用：

• 链头颜色为 $\lfloor j/b\rfloor$；
• 第二个节点颜色为 $h+(j\bmod b)$；
• 其余节点颜色全部为 $h$。

这样，一次可以加入 $bh=b(B+1-b)$ 条长链。

关键在于，新链头的颜色小于 $h$，而旧节点和新链的后续节点颜色都不小于 $h$。所以在任意节点处，所有新挂上的链都会先于原来的后续结构被遍历。

解析一条新链时，先读到链头的小颜色，再递归解析挂在链头上的其他新链。接下来读到的那个大颜色，才是该链第二个节点的颜色。两者共同确定 $j$，也就确定了这条链对应哪个叶子，以及链长 $\ell_i$。之后按照已知链长继续解析即可。

旧树节点的识别稍微精细一些。读到一个旧孩子的第一个颜色后，可能先遇到挂在它下面的新链。我们先完整解析这些新链，把它们的链头暂存起来；随后窥视第一个旧孩子的颜色，利用前面的二元组找到当前旧节点，再把暂存的新链挂上去。

这里不能简单跳过连续的小颜色，寻找下一个大颜色，因为一条新链内部本来就有大颜色。必须递归消耗完整的新链子树。实现中的 Scaffold::parse 专门处理了这一点。

因此，只要已知 $d$ 条长链，一轮就能把已知长链数推进到任意不超过 $d+b(B+1-b)$ 的位置。

三、把单点叶子变成子集计数

所有长链恢复后，整棵树的内部骨架已经确定。剩余的 $s$ 个未知叶子都只有父亲尚未确定。

此时令 $t=\lceil\sqrt D\rceil$，用 $t$ 种颜色标记辅助树，剩下 $q=B+1-t$ 种小颜色。

把未知叶子分成不超过 $q$ 组，每组至多 $g=\lceil s/q\rceil$ 个，给每组分配一种小颜色。每一轮，我们在每组中选出一个子集插球。解析返回序列后，对于每个内部节点、每个组，都能得到一个数：

这一轮选中的叶子中，有多少个以该内部节点为父亲。

于是，每个“内部节点—叶子组”对应一个未知二进制向量 $z$。我们需要选择一个二进制矩阵 $A$，使整数向量 $Az$ 唯一确定 $z$。这就是子集称重中的 detecting matrix / search matrix 问题。这里使用的是整数计数，不是模 $2$ 的线性方程组。([McGill School of Computer Science][1])

下面给出一个可以直接构造、直接解码的矩阵，不需要随机搜索。

定义 $W(r)=\sum_{a=1}^{r}\operatorname{popcount}(a)$。我们可以用 $r$ 行区分 $W(r)$ 个二进制变量。例如，$W(7)=12$、$W(9)=15$、$W(11)=20$。

把整数看成二进制位的集合。对于每个 $a=1,\ldots,r$，以及 $j=1,\ldots,\operatorname{popcount}(a)$，建立一列。令 $R_{a,j}$ 为 $a$ 中最低的 $j$ 个置位组成的集合，定义这一列在第 $x$ 行的值为

$$ A_{x,(a,j)} = [a\setminus R_{a,j}\subseteq x]\, [|x\cap R_{a,j}|\equiv1\pmod2], \qquad 1\le x\le r. $$

取满足 $W(r)\ge g$ 的最小 $r$，保留前 $g$ 列即可。每轮按矩阵对应行选择叶子，同一组中选中的叶子使用同一种颜色。

下面证明它可以唯一解码。

把一列看成布尔变量上的多重线性多项式。它等于“$a\setminus R_{a,j}$ 中的变量之积”，乘以“$R_{a,j}$ 中变量的异或”。异或多项式最高次项的系数为 $(-2)^{j-1}$，所以这一列对应的多项式只包含 $a$ 的子集单项式，其中单项式 $a$ 的系数恰好为 $(-2)^{j-1}$。

现在按 $a=r,r-1,\ldots,1$ 的顺序解码。已经解出的列，从所有观测值中减掉。

补上免费的 $y_0=0$，计算 $z_a=\sum_{x\subseteq a}(-1)^{|a|-|x|}y_x$。这是单项式 $a$ 的系数。尚未处理的其他列，其支撑集合数值小于 $a$，不可能包含 $a$，所以对这个系数没有贡献。于是得到 $z_a=\sum_j\varepsilon_{a,j}(-2)^{j-1}$，其中 $\varepsilon_{a,j}\in{0,1}$ 就是本轮要解出的变量。

这正是一个负二进制表示。不断取当前数模 $2$ 的非负余数作为下一位，再将当前数减去这一位并除以 $-2$，即可唯一恢复所有 $\varepsilon_{a,j}$。

所有用到的 $x\subseteq a$ 都满足 $x\le a\le r$，因此没有使用不存在的观测行。保留部分列也不影响唯一性，只相当于把其余变量固定成 $0$。

所以，恢复全部单点叶子只需要最小的 $r$，使 $qW(r)\ge s$。

四、参数选择、最坏上界与实现

现在所有开销都可以精确计算。

第一次 collect 已经使用一次，并恢复前 $8$ 条链。固定 $B$ 后，设 $dp_B[d]$ 表示从初始的 $a$ 条长链出发，恢复到 $d$ 条长链最少还需要几轮。

初值为 $dp_B[a]=0$。在状态 $d$，枚举 $\lceil\sqrt d\rceil\le b\le B$，这一轮最多加入 $b(B+1-b)$ 条长链。由于可以少加入一些，求出最大的容量后，更新所有能到达的状态即可。

令 $r_B$ 为单点叶子阶段所需轮数；$s=0$ 时取 $r_B=0$，否则要求 $q=B+1-\lceil\sqrt D\rceil>0$，并取满足 $qW(r_B)\ge s$ 的最小整数。总开销满足 $C\le B+1+dp_B[D]+r_B$。

枚举 $8\le B\le27$，选取开销最小的方案。

最坏 $C\le28$ 的结论来自完整的有限参数验证，而不是随机测试。只需要检查 $M=200$ 时的所有 $(D,a)$：$1\le D\le200$、$1\le a\le\min(8,D)$，以及 $s=200-D-8+a\ge0$，一共 $1544$ 组。

对于固定的 $(D,a)$，较小的 $M$ 只会减少 $s$，不会增加所需轮数，因此这已经覆盖所有 $M>8$ 的情况。精确枚举得到：

例如，$M=200,D=37,a=8$ 时，可以选 $B=17$。一轮恢复剩余长链；单点叶子有 $163$ 个，$t=7,q=11,g=15$，用 $9$ 轮恢复。总计 $K=1+1+9=11$，所以 $C=28$。

插球次数也远低于限制。第一次有 $N$ 次成功和 $M$ 次失败，之后每轮每个节点至多放一个球。由于 $B\ge8$ 且 $C\le28$，有 $K\le20$，总调用次数不超过 $KN+M\le20200$，而题目允许 $500000$ 次。

实现不含指数搜索。辅助树每轮的处理为 $O(N\log M)$；检测矩阵每组解码为 $O(r^2+rg)$，其中枚举子集的总次数也是 $O(r^2)$。这些参数在本题中都很小。

代码见 https://qoj.ac/submission/2952241 ，IOI 题就是简单。