你说得对，但是要想让字典序最小，每个子树的字典序也必须最小

我比赛的时候也这么想的
我自己的数据是
4
2 2 2 1
1 2
1 3
2 4
正确输出应该是2 2 1 2
ps题面貌似没有说是所有节点都要最稳定序列，但是答案是这么写的

荣耀黄金

出道萌新

同时达成时间&空间双击败了99%的用户

时空双修者

AK3场巅峰赛，没有困难的竞赛只有努力的狗狗！

超能小狗

AK3场挑战赛，勇敢狗狗不怕困难！

勇敢小狗

AK3场欢乐赛，成为一只快乐小狗

快乐小狗

当时我这题被卡常了一发来着（

永恒钻石

传道者

USACO

GESP8级

CSP-J一等奖

CSP-S一等奖

听 sk 说要换新一批出题人了，可能是临走前多拉一点（

题目的执行用时击败了99%的用户

时间刺客

题目的内存消耗击败了99%的用户

空间掌握者

过10道【输入输出】的官方题目

I/O·IO入门者

尊贵铂金

蛛丝马迹，难逃镜片之下。累计3次成为赛事审核志愿者。

代码纠察员

出题人

注意到这题改改可以变成树上后缀排序

秩序白银

开喷。

出题人你 $O(n\log^3 n)$ 大常数的解法开 $2\times 10^5$ 时限还只给 1s 是何意味？！

注意到 STD 是按字典序排序的，这个不是在 100 年前就被 hack 了吗？

例如

```cpp
6
1 3 2 1 3 2
1 2
2 3
3 4
1 5
5 6

```

按照官方题解来排是 `1 3 2 3 2 1`，但显然可以顺序遍历做到 `1 3 2 1 3 2` 

我认为这道题正确解法应该是：

- 首先发现是拼数的问题转到了树上，所以应该按 $S+T\lt T+S$ 排。暴力是 $O(n^2\log n)$ 的。
- 然后考虑启发式合并，依旧记录前缀哈希值。合并是 $O(n\log^2 n)$ 的。
- 排序时，先用原串 $O(n\log^2 n)$ 把非重儿子排个序，然后重儿子再用 Treap+哈希二分排序，这个也是 $O(n\log^2 n)$ 的。

这样子就能做到 2log 了。官方题解写的是啥子啊。

前面忘了后面忘了，买个 plus 吧。

分裂晶体

查询出题人精神状态

开喷。

出题人你 O(nlog⁡3n)O(n\log^3 n)O(nlog3n) 大常数的解法开 2×1052\times 10^52×105 时限还只给 1s 是何意味？！

注意到 STD 是按字典序排序的，这个不是在 100 年前就

全部评论 18