题解

思路

先把最优目标转化为“输入树未出现的最小有根树类型”，再用一条前缀链连接这个缺失类型。关键是同时证明该构造给出的上界与任意输出都必须满足的下界相等。

最优值的刻画

把输入树中所有顶点子树的同构类型记为集合 $S$。设 $T$ 是按顶点数计最小的、类型不属于 $S$ 的有根树，并令 $|T|=x$。

先说明答案不超过 $x-1$。构造一条含 $n-x$ 个顶点的链，再把 $T$ 的根接在链尾。链上每个顶点的子树都完整包含 $T$，因而不可能属于 $S$；$T$ 本身也不属于 $S$。只有 $T$ 内除根外的 $x-1$ 个顶点可能产生匹配，所以匹配数至多为 $x-1$。

再说明答案不少于 $x-1$。在任意候选树中，取顶点数不少于 $x$ 且顶点数最小的一棵顶点子树。它的每棵真子树都少于 $x$ 个顶点，而其中至少有 $x-1$ 个顶点子树。根据 $T$ 的最小性，所有少于 $x$ 个顶点的有根树类型都属于 $S$，所以至少有 $x-1$ 个匹配。

因此最优值恰为 $x-1$。若最小缺失类型比整棵输出树还大，则所有不超过 $n$ 个顶点的类型都已出现，直接输出原树即可。

枚举最小缺失类型

一棵有根树的同构类型由根的各棵儿子子树类型的多重集合唯一决定。按顶点数从小到大枚举类型；同一大小内，要求儿子类型编号非递减，就能不重不漏地枚举所有无标号有根树。

对输入树自底向上处理。只需记录大小不超过 $15$ 的顶点子树，并把排序后的儿子类型编号序列映射成一个精确类型编号。随后扫描枚举表，找到第一个未在输入树出现的类型。

为什么枚举到 $15$ 一定足够：大小恰为 $15$ 的无标号有根树超过 $87000$ 种。若它们全都在输入树中出现，这些对应的顶点子树互不相同，且每棵都有 $15$ 个顶点；由子树的包含关系可推出所需顶点总量超过 $10^6$，与限制矛盾。因此在大小不超过 $15$ 时一定已经出现缺失类型。

最后按类型表递归还原 $T$，在它之前接上所需长度的链即可。还原深度至多 $15$；输入树本身使用迭代遍历，避免深链递归爆栈。

做法

1. 自底向上给输入树中大小不超过 $15$ 的顶点子树分配精确同构类型编号。
2. 按大小枚举全部不超过 $15$ 点的无标号有根树，找到输入中第一个没有出现的类型 $T$。
3. 若 $|T|>n$，输出原树；否则输出一条 $n-|T|$ 点的链，并把 $T$ 的根接到链尾。

子任务算法

• 子任务 1：用 Prüfer 序列枚举所有标号树，逐一精确计算匹配数，取最优者。
• 子任务 2：链缺失的第一个类型是三点叉形，星形树缺失的第一个类型是两点链，可直接构造。
• 子任务 3：用规范括号串表示每棵顶点子树并枚举缺失类型，字符串总长度在该范围内可承受。
• 子任务 4：使用整数类型编号和按大小枚举的完整类型表。

正确性结论

上述下界证明说明任何输出至少产生 $x-1$ 个匹配；链加最小缺失树的构造达到这个下界，所以输出必然最优。类型编号由完整的儿子类型多重集合决定，故缺失类型的判定与有根树同构定义等价。

复杂度

输入树的类型处理需要对子类型排序，总时间为 $O(n\log n)$，类型枚举只涉及大小不超过 $15$ 的固定有限表。空间复杂度为 $O(n)$。