ARC095D Permutation Tree

题意：对于一个排列 ，按如下规则构造一棵树。

对于每一个 ，找到最大的 使得 ，然后在 间连边。

给出树 ，若可以构造出与 同构的树，则给出字典序最小的排列 ，否则指出无解。

，时限 。

---

先考虑给定排列 如何生成对应的树。

考虑 的逆排列 。

• 对于每一个 ，找到最大的 使得 ，然后在 间连边。

这条规则变为：

• 对于每一个 ，找到最大的 使得 ，然后在 间连边。

也就是说， 会向 连边。

最终产生的树是这样的 ： 每个位置向自己前方的最大值连边，所有前缀最大值形成一条链，其余的点连接在链上，形成一条毛毛虫。

所有毛毛虫都是可以构造出来的。

判定 是否为毛毛虫（找直径即可），然后按如下规则构造 ：

设直径两端分别为 ，从两者分别开始一次。

• 结论： 字典序最大 字典序最小。（ 指 的逆的反转 ）

于是，从末端开始从大到小贪心标号。先编号直径上的点 ，然后把周围的其他点依次编号，再编号直径上的下一个点。

复杂度 。