题解

思路

把所有原树中的叶子一次性删除。若剩余结点形成一条路径（也允许为空或只有一个结点），原树称为毛毛虫树。

题目所求的循环排列存在，当且仅当原树是毛毛虫树。

做法

子任务 1：排列枚举

固定第一个结点，枚举其余结点的排列，逐一检查相邻项和首尾项的树上距离。复杂度 $O(n!\,n)$。

子任务 2：子集动态规划

先建立树的平方图：原树距离不超过 $2$ 的两个结点在新图中连边。固定起点 $1$，令

表示存在一条从 $1$ 出发、恰好访问集合 $S$、终点为 $v$ 的简单路径。枚举最后一步转移，并在全体结点访问完后检查 $v$ 能否回到 $1$。复杂度 $O(2^n n^2)$，实现时用位集枚举相邻点可降到 $O(2^n n)$ 次状态转移。

满分算法

判定

把度数大于 $1$ 的结点标为核心结点。由于原图是树，这些核心结点连通。它们的诱导子图是一条路径，当且仅当每个核心结点在核心中的度数不超过 $2$。若某个核心结点的核心度数至少为 $3$，输出 No。

构造

设核心路径为 $q_0,q_1,\ldots,q_k$。若核心为空，则 $n=2$，直接把两个结点作为路径。对每个路径结点，把与它相邻但不在路径上的叶子记为一组。

按以下顺序输出：

1. 从左向右扫描路径。偶数下标处输出该结点的所有外挂叶子，奇数下标处输出路径结点本身。
2. 从右向左扫描路径。奇数下标处输出该结点的所有外挂叶子，偶数下标处输出路径结点本身。

每个结点恰好输出一次。同组叶子间距离为 $2$；一组的边界与相邻路径结点或相邻组的边界距离也不超过 $2$。首尾连接处同样满足这一性质，因此得到合法循环排列。

正确性证明

若核心诱导子图有度数至少为 $3$ 的结点，删去该结点后至少有三个分支都包含核心结点。循环遍历要在这些分支之间切换，但一次距离不超过 $2$ 的跳跃只能越过中心连接两个分支；对循环中各分支的进入和离开计数会迫使中心附近的结点被重复使用，故不存在所求排列。

反之，若核心诱导子图是一条路径，构造中所有相邻输出要么同属一组叶子、要么隔着一个路径结点、要么是相邻的路径结点，距离均不超过 $2$。构造恰好输出所有路径结点和所有外挂叶子各一次，且最后一项到第一项也至多跨过一个路径结点。因此构造必然合法。

综上，算法的判定与构造均正确。

复杂度

满分算法仅遍历常数次树，时间复杂度 $O(n)$，空间复杂度 $O(n)$。