APIO2024 C 题解 最后更新于 2025-05-01 22:51:15

考虑对 $x$ 二进制拆位。 我们用 $80$ 个点来维护二进制下每一位，假若交互器随机删点那么这一位彻底丢失的概率只有 $2^{-80}$ 即使需要 $60$ 位都正确也是很轻松的。问题是如何用点维护 $0,1$ 信息？ 考虑对于点 $u$ 随机两个父亲 $fa_{u,0/1} < u$ 由于编号都比自己小，故一定构成树，那么当其维护的位信息是 $0$ 时将父亲设置为 $fa_{u,0}$ 否则为 $fa_{u,1}$，由于这两个值都是随机的所以树的形态实际上也是随机的。 然后你发现交互库可能使用特殊策略删边，没关系，随机一个置换并将边的端点编号置换掉，那么相当于构造出来的树编号随机且形态随机，每条边代表哪一位的信息也是随机，交互库删点过程也等价于随机。 注意到将底数更换为 $k$ 也就是使用 $k$ 进制拆位也是可行的，并且应该能得到更低的所需点数。 记得将不同位的信息均匀地放在原序列中以及随机置换打乱树的编号。 事情到这里应该结束了。 但是发生了神秘的事件。 有好心人发现我的代码更换种子后会爆炸。 并且并不是因为丢失信息，因为答案变大了而我的写法中丢失了信息答案会减少。 这个时候 milmon 老师说：  （此处 $faA,faB$ 就是 $fa_{u,0},fa_{u,1}$）  由于不是每一次都有这么好的运气，所以说要记得判重。 [参考代码](https://qoj.ac/submission/1011495)