题解

思路

删除边 $(u,v)$ 时，它与其余边相邻的数量是 $\deg(u)+\deg(v)-2$。因此合法删除的充要条件是当时 $u,v$ 的剩余度数奇偶性相同。

把一条边称为“奇边”，表示删除它时两端度数均为奇数；否则称为“偶边”。考察某个顶点处相 incident 的边：每删除一条 incident 边，该顶点的剩余度数奇偶性翻转，所以这些边按删除先后必须奇偶交替，并且最后一条一定是奇边。因此：

• 顶点度数为偶数时，奇边与偶边数量相同；
• 顶点度数为奇数时，奇边比偶边恰好多一条。

将树根设为 $1$。从叶子向根处理，子边的类型已经确定。对于非根顶点，还可以选择父边的类型。若当前偶边数不少于奇边数，就把父边设为奇边；否则设为偶边，使两类数量尽量平衡。若最终无法满足“奇边数等于偶边数或恰好多一条”，则无解。叶子的父边自然会被设为奇边。

若所有顶点都满足条件，则在每个顶点把 incident 边排成奇偶交替、以奇边结束的局部顺序。对子边位置递归处理整棵子树，对父边位置直接输出该边。这个嵌套顺序同时满足每个顶点的局部顺序，因而每次输出的边两端剩余度数奇偶性相同。

做法

子任务一

当 $n\le12$ 时，用一个二进制状态表示尚未删除的边。枚举当前所有相邻边数为偶数的边并递归删除，记忆化每个状态是否可行，同时记录一条成功转移以恢复答案。

子任务二

最大度数不超过 $2$ 时，树是一条路径。若 $n$ 为奇数，则路径有偶数条边且无解；若 $n$ 为偶数，按路径顺序将边记为 $e_1,e_2,\ldots,e_{n-1}$，依次输出

每个偶数编号边删除时有两条相邻边，紧接着的奇数编号边删除时没有相邻边，最后一条边也没有相邻边。

子任务三

直接按“思路”中的方法递归处理。第一次 DFS 自底向上确定父边类型，第二次递归按照每个顶点处的奇偶交替顺序构造答案。深度不超过 $4000$ 时系统递归栈可以安全承载。

满分做法

1. 迭代建根树并得到后序遍历。
2. 按后序遍历确定每条父边的奇偶类型，并检查每个顶点的数量条件。
3. 对每个顶点分别收集奇边和偶边，按顶点度数的奇偶选择起始类型并交替取边。
4. 用显式事件栈展开上述递归构造，避免链状树使系统递归栈溢出。

复杂度

子任务一的时间复杂度为 $O(2^n n^2)$，空间复杂度为 $O(2^n)$。

子任务二、子任务三与满分做法的时间复杂度均为 $O(n)$，空间复杂度均为 $O(n)$。多组测试的复杂度对所有 $n$ 求和。