题解：非交叉的1212子序列¶
出题人建模：将1、2视为括号，用栈配对后得到嵌套森林。Codex（GPT-6）给出该建模的交换证明，发现最长单链贪心的反例，并以森林不可比图的匹配亏量动态规划完成线性时间、流式实现。
先固定1到2的配对¶
把1视为左括号、2视为右括号。从左到右扫描，遇到2时与最近的未配对1匹配；没有可用1时忽略该2。未匹配的1最终也不构成节点。每条配对线成为一个节点，直接包含关系构成森林。
为什么可以固定这些配对？等价地，不断从剩余字符串中删除相邻的12并固定为一对。取任意最优合法选法，考察下一对相邻端点 \(p,q\) ：
- 两端都未使用时，不必选择这条固定配对。
- 已经互相配对时，保持不变。
- 只有一个端点用于某条配对时，把该配对缩短为 \((p,q)\) .另一端被释放，配对所属的1212仍然合法，因为缩短不会碰到其另一条、不相交的配对。
- 两端分别用于不同配对时，这两条线必定交叉，故合法选法中不会出现这种情况。
这里“相邻”指删除已固定配对后的相邻。尚未固定的端点没有位于二者之间；之前固定的配对不会跨过尚未删除的端点，所以缩短也不会与它们交叉。每次调整保留所选1212的数量。全部删除结束后，剩余串只有若干2再接若干1，不再可能含有未固定的1到2配对。由此得到只使用栈配对、数量不减的选法。
反过来，栈配对之间天然不交叉。森林中互不可比的两个节点，对应两条先后分离的配对线，其四个端点按顺序恰好构成1212。因此问题等价于：在森林节点中配出最多组，每组两个节点互不为祖先，且每个节点最多用一次。
合并不同子树的匹配¶
对森林中的第 \(i\) 棵树，记节点数为 \(s_i\) ，内部最大匹配后剩余的节点数为 \(d_i\) ，称为匹配亏量。不同树的任意两个节点都可配对。令 \(S=\sum s_i\) ，整个森林的最小剩余数为
空森林取 \(D=0\) .下面证明该公式。
任何匹配都受到奇偶性限制，至少剩下 \(S\bmod2\) 个节点。对树 \(i\) ，内部至多消去 \(s_i-d_i\) 个节点，外部只有 \(S-s_i\) 个节点可与它配对，因此至少剩下 \(d_i-(S-s_i)\) 个。以上给出下界。
为了达到下界，先在每棵树内部取最大匹配，再不断配对来自不同树的剩余节点，直到未匹配节点只在一棵树 \(T\) 中。若还剩至少两个，就找一条两端都在 \(T\) 外的已有匹配边，拆成两条与 \(T\) 内剩余节点相连的边，匹配数增加一。
继续直到只剩零或一个节点，达到奇偶下界；或者不存在完全位于 \(T\) 外的匹配边。后一种情形下，全部外部节点都已经与 \(T\) 内节点配对，\(T\) 原有的内部最大匹配未被拆掉，剩余数恰为 \(d_T+s_T-S\) .因此上述下界一定可达。
一棵树的根不能与自己的任何后代配对，所以先合并其所有孩子组成的森林，再令节点数和亏量各加一。
两个整数即可汇总一层¶
每个栈帧只保存孩子子树的节点数总和 \(S\) ，以及 \(M=\max_i(s_i+d_i)\) .某个1与2闭合时，得到
然后把这棵子树并入父帧。扫描结束时，没有闭合的1不是节点，将它们的孩子森林直接合并到外层，不额外增加节点或亏量。最终虚根表示整个森林，答案为 \((S-D)/2\) .
每个字符只进出栈一次，时间 \(O(n)\) ，空间 \(O(n)\) ；不用存储整棵树或递归遍历。实现每层只存两个整数，避免深链导致调用栈溢出。
最长单链贪心的反例¶
出题人的“优先选择最长单链所在分支，再任取另一分支配对并拆根”贪心不能保证最优。字符串
11221122111112222122
会使该策略得到4，但下列五组位置都合法：
它们使用全部20个位置，没有1到2配对线交叉，因此达到上界5。错误原因是单链长度不能刻画整个分支需要从外部获得多少匹配；亏量公式保留了这个信息。该反例在修正输入字符映射之后仍然成立，不是字符读错造成的假反例。
标准程序使用亏量动态规划。验证包括长度不超过12的全部8191个二进制字符串的直接子序列打包检查，以及千万字符的闭式结构测试，见测试说明和性能记录。