官方题解只能做到 $n-4$ 次？玩得太差了。这题可以做到确定性的 $\frac{201}{202}n-O(1)$ 次翻点，编码和解码的时间、空间复杂度均为 $O(n)$。更精确地，对于 $n\ge5$，有

$$ \boxed{m\le\min\left\{n-4,\ n-\left\lceil\frac{3n+1463}{606}\right\rceil\right\}.} $$

当 $n=300000$ 时，最坏不超过 $298512$ 次。$n=4$ 时最坏需要 $1$ 次；所有规模均使用下面的统一构造。

题目要求发送方在一棵初始全白的树上依次翻点，接收方只能知道点数 $n$、操作数 $m$ 和每次操作后的异色边数 $a_i$，最后还原一棵同构树。核心是让不同树形使用不同的编码：末端多时省掉整簇叶子，叶子多时只遍历骨架，长链多时直接发送压缩后的拓扑和链长。发送方计算各个适用编码的实际长度，取最短者。

从异色边数恢复树

令 $a_0=0$，记 $d_i=a_i-a_{i-1}$。若一个白点 $u$ 有 $t$ 个黑色邻居，将它翻黑的增量就是

$$d_i=\deg_T(u)-2t.$$

因此，后序翻点时，父亲白、孩子全黑，增量为 $2-\deg_T(u)$；先序翻点时，只有父亲黑，增量为 $\deg_T(u)-2$。根没有父亲，先序翻根的增量为它的度数。

将原树的叶子删除一轮，得到的树记为 $C$，称为骨架。定义 $L$ 为原树叶子数，$I=n-L$ 为骨架点数，$K$ 为骨架中度数为 $1$ 的点数，$J$ 为骨架中度数至少为 $3$ 的点数，$S$ 为所有骨架末端直接连接的原树叶子总数。

星形树用空序列表示，路径用单项观测 $[2]$ 表示，后者只需翻转任意一个度数为 $2$ 的点。

其余情况满足

$$I\ge2,\qquad 2\le K\le S\le L,\qquad J\le K-2.$$

取原树度数最小的骨架末端 $r$ 为根，并固定它的一片原树叶子 $z$。下面的 A、B、C、D 是四种消息格式，接收方可以直接区分它们。

A：末端星形的后序编码

根 $r$ 及其叶子全部不翻。对其余点按后序处理：若 $u$ 是骨架末端，只翻中心 $u$，跳过它的全部叶子；其余点正常翻转。

骨架末端被翻时，所有邻居都是白色，增量为 $d=\deg_T(u)\ge2$。这个操作便表示一个中心带有 $d-1$ 片叶子的有根星形子树。

普通点被翻时，所有孩子都已变黑，父亲尚未变黑，增量为 $d=2-\deg_T(u)\le1$，所以它有 $1-d$ 个孩子。

接收方维护一个子树根栈。遇到 $d\ge2$，新建一个中心和 $d-1$ 片叶子，将中心入栈；遇到 $d\le1$，新建一个点，从栈顶弹出 $1-d$ 棵子树作为它的孩子，再将它入栈。这正是后序遍历的还原。

序列读完后，栈中恰有一棵树。新建根 $r$ 与它连接，将剩余顶点全部作为 $r$ 的叶子。剩余数量由 $n$ 确定。

省略的点恰好是根和计入 $S$ 的叶子，因此

$$\boxed{m_A=n-S-1.}$$

B：骨架的先序编码

先翻转 $z$ 两次，得到观测前缀 $(1,0)$，恢复全白。随后按骨架先序翻转骨架点，跳过所有原树叶子。

根的增量为原树度数，其余骨架点的增量为原树度数减 $2$。这些增量全部非负。为了告诉接收方每个点在骨架中的孩子数 $c$，在翻点后放置控制标记：$c=1$ 时不放标记，$c=0$ 时放一个标记，$c\ge2$ 时放 $c$ 个标记。

每个标记都是将 $z$ 翻转两次。此时父亲 $r$ 一直为黑色，$z$ 在标记前后都是白色，所以标记产生的两个增量恰为

$$(-1,+1).$$

普通骨架点的增量非负，标记以 $-1$ 开始，因此可以唯一解析。接收方得到原树度数和 $c$ 后，便知道这个点的原树叶子孩子数为

$$\deg_T(u)-c-[u\ne r].$$

用一个记录剩余孩子槽位的栈，就能按先序还原骨架，并给每个点补上叶子。

先序遍历的最后一个骨架点一定是骨架叶子，它的翻点操作和一个控制标记都不发送。接收方读到末尾时恰好剩下一个孩子槽位，在这里补一个点，再将剩余顶点全部作为它的叶子即可。

以骨架末端为根后，有 $K-1$ 个骨架叶子，$J$ 个至少有两个骨架孩子的点，后者的孩子数总和为 $K+J-2$。完整遍历的标记数为

$$M=(K-1)+(K+J-2)=2K+J-3.$$

计入前缀，省略最后一个点及其标记，操作数为

$$ \boxed{m_B=2+(I-1)+2(M-1)=n-L+4K+2J-7\le n-L+6K-11.} $$

C：压缩拓扑和链长

将原树所有度数为 $2$ 的点压缩掉，得到一棵边带正整数长度的树。它仍有 $L$ 个叶子，其余点的度数至少为 $3$。设边数为 $E$，则

$$E\le2L-3.$$

这个有权树用二进制编码，再通过翻点发送。

先翻转 $z$ 四次，得到格式前缀 $(1,0,1,0)$，恢复全白。之后每一位使用两次操作：位 $0$ 翻转 $z$ 两次，产生观测 $(1,0)$；位 $1$ 翻转 $r$ 两次，产生观测 $(\deg_T(r),0)$。因为 $\deg_T(r)\ge2$，两种位可以区分，而且每一位结束后都恢复全白。

以叶子 $z$ 为根。根及其唯一孩子槽位事先约定，只发送其余点的先序序列：叶子发送 $1$；有 $c\ge2$ 个孩子的分支点发送 $0$、$c-2$ 个 $1$、再发送 $0$。

孩子槽位全部填完时，拓扑恰好读完，所以不必额外发送拓扑长度或 $E$。除根外有 $L-1$ 个叶子，分支点的孩子数总和为 $E-1$，拓扑恰好占用

$$L+E-2$$

位。

接着按新点的先序顺序发送它到父亲的边长 $\ell_i$，其中

$$\ell_i\ge1,\qquad\sum_{i=1}^{E}\ell_i=n-1.$$

双方根据 $n,E$ 共同选取整数 $b\ge0$，将

$$\ell_i-1=q_i2^b+r_i,\qquad0\le r_i<2^b$$

编码成 $q_i$ 个 $1$、一个 $0$，再加上 $r_i$ 的 $b$ 位二进制表示。长度编码的位数为 $E(b+1)+\sum_iq_i$，而

$$\sum_iq_i\le\left\lfloor\frac{n-1-E}{2^b}\right\rfloor.$$

取使

$$U_b=E(b+1)+\left\lfloor\frac{n-1-E}{2^b}\right\rfloor$$

最小的 $b$，平局取较小值。只需枚举 $0\le b\le\max(3,\lfloor\log_2n\rfloor)$。接收方采用同一规则，无须发送 $b$。

读出全部边长后，将压缩边展开即可。计入前缀和每位的两次操作，实际长度为

$$\boxed{m_C=2L+2E(b+2)+2\sum_iq_i.}$$

所选 $U_b$ 不大于 $U_3$，因此

$$ \begin{aligned} m_C &\le2L+10E+2\left\lfloor\frac{n-1-E}{8}\right\rfloor\\ &\le2L+\frac{39}{4}E+\frac{n-1}{4}\\ &\le\boxed{\frac{43}{2}L+\frac{n-1}{4}}. \end{aligned} $$

这里将 $E\le2L-3$ 放宽为 $E\le2L$。若使用候选 $b=\lfloor\log_2((n-1)/E)\rfloor$，还可得到 $m_C<18L+4L\log_2\frac{n-1}{2L}$，所以叶子少、长链多时这个格式很短。

D：两端各有一片叶子的骨架路径

当 $S=2$ 时，必有 $K=2$，骨架是一条路径，且两端各连接一片原树叶子。记骨架为 $v_1,v_2,\ldots,v_I$，中间各点连接的叶子数为 $\ell_2,\ldots,\ell_{I-1}$。原树不是路径时，这些中间叶子至少有一片。

若 $I\ge4$，只依次翻转

$$v_2,v_3,\ldots,v_{I-1},$$

得到的增量为

$$\ell_2+2,\ell_3,\ldots,\ell_{I-1}.$$

如果中间叶子全挂在 $v_2$ 上，就反转路径方向。这样可以保证观测非递减，且最后一项严格大于第一项。

接收方建立一条 $m+2$ 点的骨架路径，两端各加一片叶子；给第一个被翻转的点添加 $d_1-2$ 片叶子，其余被翻转的点分别添加 $d_i$ 片叶子。操作数为

$$\boxed{m_D=I-2=n-L-2\le n-5.}$$

若 $I=3$，树形由 $n$ 唯一确定：中间点连接两条长度为 $2$ 的臂，再连接 $n-5$ 片叶子。翻转任意叶子，用单项观测 $[1]$ 表示这棵树。

消息格式的识别

先识别三个特殊消息：$m=0$ 表示星形树，$m=1,a_1=2$ 表示路径，$m=1,a_1=1$ 表示 D 的三点骨架情况。

其余消息中，若观测非递减且 $a_m>a_1$，则使用 D。否则，前两项不是 $(1,0)$ 时使用 A；前两项为 $(1,0)$ 且第三项大于 $1$ 时使用 B；前四项为 $(1,0,1,0)$ 时使用 C。

A 的每一步都有黑点，而根始终为白色。树连通，所以异色边数一直大于 $0$，不会与 B、C 的前缀混淆。B 的第三项是 $\deg_T(r)\ge2$，C 的第三项是 $1$，二者也可以区分。

若 A 的观测非递减，它不能包含度数至少为 $3$ 的普通后序节点，否则会出现负增量。因此骨架只能是一条路径，中间没有原树叶子，整个观测序列是第一个星形中心产生的正数，之后一直不变。这与 D 的 $a_m>a_1$ 不同。B、C 的前两项已经下降，也不可能被识别为 D。

A 若只有一个操作，骨架就只有两个点。因为根选择度数较小的那个，非路径情况下被翻转的另一个点度数至少为 $3$，不会产生单项观测 $[1]$ 或 $[2]$。B、C 的消息长度都大于 $1$。因此所有格式都可以唯一识别。

最坏操作数

令最终节省的操作数为 $q=n-m$。A、B 给出

$$q\ge S+1\ge K+1,\qquad q\ge L-6K+11.$$

第一个不等式乘以 $6$，再加上第二个，得到

$$7q\ge L+17.$$

C 给出

$$4q\ge3n+1-86L.$$

将前一个不等式乘以 $86$，与后一个相加，消掉 $L$：

$$606q\ge86(L+17)+3n+1-86L=3n+1463.$$

因此

$$m\le n-\left\lceil\frac{3n+1463}{606}\right\rceil.$$

另一方面，$S\ge3$ 时 A 不超过 $n-4$；$S=2$ 的非路径树由 D 保证不超过 $n-5$。星形树不需要操作，路径只需要一次操作；D 的三点骨架情况也只需要一次操作，且非路径时 $n\ge6$。这些特殊情况同样满足上述界，因此得到开头对所有 $n\ge5$ 的完整上界。

几个规模下的最坏保证为：$n=1000$ 时 $m\le992$，$n=10000$ 时 $m\le9948$，$n=100000$ 时 $m\le99502$，$n=300000$ 时 $m\le298512$。这些数值来自上述证明。

当前构造在 $n=4,5$ 时的精确最坏值均为 $1$，在 $6\le n\le17$ 时的精确最坏值为 $n-4$；这里的精确值只针对本构造，不声称是所有方案中的最优值。$18\le n\le320$ 保证不超过 $n-4$；$n\ge321$ 时，开头的通用上界严格优于 $n-4$。对任意 $n$，星形树均可用 $0$ 次操作表示。

线性级别的下界

取一条有 $k+10$ 个点的主链，在中间连续的 $k$ 个点上各接一个四点有根挂件。每个挂件独立选择：以端点为根的四点路径；或者根有两个孩子，其中一个是叶子，另一个还有一个叶子孩子。

树的最大度数不超过 $3$，点数为 $n=5k+10$。主链两端各留五条边，挂件的高度不超过四，所以主链是唯一的直径。同构至多反转主链，因此 $2^k$ 种选择至少产生 $2^{k-1}$ 种不同树形。其他点数可在主链一端延长至多四条边，同样满足这个计数下界。

最大度数不超过 $3$ 时，每次翻点的增量只能属于 $\{-3,-2,-1,0,1,2,3\}$。若最坏至多翻 $M$ 次，连同消息长度在内，可用消息数小于 $7^{M+1}$。因此

$$7^{M+1}>2^{k-1},\qquad M>(k-1)\log_7 2-1=\Omega(n).$$

所以最坏次数不能降为 $o(n)$；这里没有证明线性项系数 $201/202$ 最优。

复杂度

A、B、D 的操作序列均可在线性时间生成。C 中候选 $b=0$ 给出 $U_0=n-1$，所以所选链长编码的位数也是 $O(n)$；枚举 $b$ 只需 $O(\log n)$ 时间。所有树的遍历均使用显式栈。

因此，两次运行的时间、空间复杂度均为 $O(n)$。