根据不同做法，我们设置了一个额外评测链接，仅修改了 $n$ 的范围上限。

目前评测机对于专门卡常数的提交评测比其他 OJ 要慢一点（非卡常的代码性能表现基本差不多），但是依旧满足 2 倍 std 的时间限制，因此时空限制依旧合理，保持不变。有精力的情况下，会持续对时间 2log 以上以及空间 1log 以上的做法出 Hack 数据（至少现有已知的这些做法都卡掉了，在其他较快的 OJ 测了也无法通过）。但是滥用本题评测将会被封号处理。

时间限制： 3.0 秒

空间限制： 1024 MB

题目描述

西西艾弗岛上某实验室设计了一套包含 $n$ 个字符的字符集，字符从 $1$ 到 $n$ 编号。本题中，我们无需关心这些字符具体是什么，只需用整数编号对其进行指代即可。

现有一棵 $n(n > 1)$ 个节点的简单树，每个节点有一个字符串。初始时，第 $i(1\le i\le n)$ 个节点的字符串只包含一个编号为 $i$ 的字符，也就是说 $n$ 个节点的所有字符构成了字符集 $\{1,2,\cdots,n\}$。

你可以对某一个节点进行一次「聚拢」操作：

• 将这个节点的字符串，和所有与它相邻节点的字符串一起进行重排（可以任意决定这些字符串的拼接顺序），重排后合并成一个字符串，作为这个节点的新字符串；所有与它相邻节点的字符串均被清空为空串。

你可以执行任意次操作，但是必须保证：

• 除了第一次操作，每次操作参与的字符串（在执行聚拢操作的节点或邻域节点上的字符串）中一定有一个字符串长度 $\ge 2$。

你需要最后将树上所有字符合并到一个字符串里，作为最终串。

求能够得到的字典序最小的最终串。

输入格式

从标准输入读入数据。

第一行包含一个正整数 $n$，表示树上的点数。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示树上的一条边。

输出格式

输出到标准输出。

输出一行 $n$ 个由空格分隔的整数，表示字典序最小的最终字符串。

7
3 5
5 7
3 1
2 5
3 4
6 4

1 2 3 5 7 4 6

样例 1 解释

样例对应的树结构为：

可通过以下 $3$ 次合法的「聚拢」操作得到字典序最小的最终串：

1. 对节点 $5$ 操作：合并 $2, 3, 5, 7$ 号点的字符，按升序拼接得 2 3 5 7。此时全树仅有这一个串长度 $\ge 2$。（其余参与点均清空，下同）
2. 对节点 $3$ 操作：合并 $1, 3, 4, 5$ 号点。拼接顺序为 $s_1 + s_5 + s_4$，得到 1 2 3 5 7 4。
3. 对节点 $4$ 操作：合并 $3, 4, 6$ 号点。拼接顺序为 $s_3 + s_6$，得到 1 2 3 5 7 4 6。

操作结束后，所有字符成功合并为一个字符串，即为答案。

子任务

本题无数据梯度，需要通过全部数据获得所有分数。对于所有测试数据，满足 $2\le n\le 10^6$，保证输入是一棵合法的树。

提示

本题输入输出量较大，请采用效率较高的输入输出方式。

附录 1

“我要战斗，与所有错误行使力量的人战斗。” / “只有做好了被枪击觉悟的人，才有资格开枪。”——鲁路修《Code Geass》

“不对！所谓觉悟，是把自己的命也押上去。”——蒙奇·D·路飞《ONE PIECE》

“不是因为有胜算。只是因为必须打倒他，所以我就去打倒他，仅此而已。”——黑崎一护《BLEACH》

“我战斗的目的，无论过去还是现在都只有一个，为了我自己的正义。”——斋藤一《浪客剑心》

“即使这样的人生充满伪善，我也会继续坚持成为正义的伙伴！”——卫宫士郎《Fate/stay night UBW》

“我有想守护的东西。那就是，平凡得不能再平凡的日常。”——立花响《战姬绝唱 Symphogear》

“为了保护那些仅靠所谓‘正义’无法保护的东西。”——月读调《战姬绝唱 Symphogear G》

附录 2

对"GPT 話你知": Thoses tasks surpassed by LLMs 的拙劣模仿。

官方题解时间复杂度 $O(n\log n)$、空间复杂度 $O(n)$，第一版这么冗长（这么长的一坨史山还被其他 AI 当成语料了），后面才简化到 100 多行（而且还是 $O(n\log^2 n)$ 的）？玩的太差了。不妨来点思考链更简单的做法，还不用在原树上分类讨论下一步走几条边。

题解

记 $N[u]$ 为闭邻域，$Q(u)$ 为它的升序串，$b(u)=\min N[u]$。固定第一次聚拢中心 $r$，每次把新儿子中小于大串串首的部分放左边，其余放右边。若依次产生左段 $L_1,\ldots,L_s$，答案便是 $L_s\cdots L_1Q(r)$ 接上各次右侧输出。取出严格递增短串 $W(r)=L_s\cdots L_1Q(r)$，先比较这些短串的继续前缀，再比较结束点的真实后缀。

相对于根 $r$，沿原树路径不断刷新 $b$ 的严格最小值，就得到产生左段的记录中心。把中心按 $(b(u),u)$ 排序，反复删除最小中心、递归处理剩余分量，构造消元树。沿消元根到 $r$ 的祖先链，每段同权中心只保留最后一个，正好是 $r$ 的记录序列。

因此消元边 $u\to v$ 应输出 $Q(u)$ 中严格小于 $b(v)$ 的前缀，最后再接完整的 $Q(r)$。为每个中心只建一条 $Q(u)$ 字符链，把儿子链接到这个前缀末尾；零长度前缀则共用父链之前的位置。全部闭邻域长度之和只有 $3n-2$，加一个虚根后，这棵字符树只有 $3n-1$ 个节点。每个根对应一个终点，根到终点恰好输出它的 $W(r)$。

在字符树上，每轮找当前前沿后继的最小字符，并保留全部同字符后继，得到递增路径 $P_1,\ldots,P_M$。已经结束的短串留给下一步比较，结束符不参与继续字符的大小判断。再遍历一次，求各根首次失配或提前结束的时刻 ban，并令 id[u] 为标签在 $P$ 中的位置，未出现记零。

若 $N[u]$ 全部出现在 $P$ 中，中心 $u$ 在 $\tau(u)=\max\limits_{v\in N[u]}id[v]$ 时完成。它完成时仍匹配前缀，就恰好是这一轮的合法结束根。逐轮激活完成中心，用并查集合并相邻中心。

对第 $k$ 轮结束根所在分量 $C$，记 $t$ 为 $P_1,\ldots,P_k$ 中最后一个不属于 $N[C]$ 的位置，没有记零。补完不输出右段的操作后，真实大串就是 $P_{t+1}\cdots P_k$。下一继续字符为 $P_{k+1}$，末轮设为 $n+1$。

严格胜出可以压成一个阈值。对出现在 $P$ 中的中心 $u$，令它的非零邻点位置为 $q_1<\cdots<q_d$，$a(u)$ 为不在整条 $P$ 中的最小邻点，定义 $g(u)=\min(\{id[u]\}\cup\{q_i+1:q_i+1<q_{i+1}\})$、$e(u)=\max(id[u],|\{i:P_i<a(u)\}|)$。若 $a(u)$ 不存在，不建立这项贡献。

中心已经收入、剩余块能参与比较、未读首字符小于继续方向，合起来就是 $e(u)\le k$ 且 $g(u)>t$。预处理 $D_k=\max(\{0\}\cup\{g(u):e(u)\le k\})$，结束根严格胜出当且仅当 $D_k>t$。

等价地，$D_k>0$ 且窗口 $P_{D_k},\ldots,P_k$ 被 $N[C]$ 完全覆盖。完成分量不会覆盖未来字符，所以可以直接维护静态后缀 $\{P_l,\ldots,P_M\}$ 的覆盖数，令 $l=\max(1,D_k)$ 单调右移。树上两个相邻分量的闭邻域交集只有连接边两个端点，合并时扣重；删除标签时，更新它所在的完成分量，或它各个已完成邻点所在分量。

选出首个严格胜出的结束根，截断 $P$ 得到准确的 $W(r)$。重新定根，不在这段 $W$ 中的儿子就是各中心的右载荷。倒扫 $W$ 的父亲连续段，恢复左记录执行链。建立原父亲依赖与记录链依赖，空载荷优先，其余按最小右首做拓扑排序，连续输出每个任务的完整右段。若一开始 $M=n$，直接输出 $P$。

正确性与复杂度

记录与消元。 祖先必须先展开，非记录中心已有记录祖先提供更小串首，只有记录中心会产生左段；独立左目标先处理较大者的交换，使记录按值递减执行。消元树祖先性质由路径最小值归纳得到。同权 $b(u)=b(v)=z$ 时，两中心都在 $N[z]$ 内；同权祖先链靠前的中心在原树朝根方向还会遇到同权中心，因此不是严格记录，最后一个才保留。对升权边，朝根的原邻点 $p$ 满足 $b(v)\le b(p)\le\min(u,p)$，故父链截取的部分排除了 $u,p$，恰好是新收入的左段。于是每个终点字符串都精确等于 $W(r)$。

共享与筛选。 每条中心链只有一个接入位置，保留父链继续边及全部儿子分支后仍是一棵树，终点路径没有遗漏。逐轮保留全部最小字符后继，按前缀长度归纳即得精确的短串前沿。完成时刻与首次失配时刻共同精确识别结束根。

首差与覆盖。 已展开中心属于结束根的完成分量。若最后一个尚待实际收入的左字符已经被该分量闭邻域覆盖，唯一路径上的中心都已完成，其右段为空，应继续补完，矛盾。因此空操作对齐后真实大串由最后覆盖缺口确定。中心自身位置与邻点断档给出 $g(u)>t$，整条 $P$ 之外最小邻点的排名给出 $e(u)\le k$，二者精确描述严格更小的合法右首。对中心取存在量词得到 $D_k>t$，再等价改写为窗口全覆盖。并查集的扣重公式由原树无环保证，静态后缀与当前窗口的交集相同。

结束分支的比较。 更大的真实下一字符立即落败；相等时，确实存在匹配的继续短串，产生相等字符的已暴露中心可以接管：将其未读右块对应到新根块的剩余部分，完整读完此块并补空操作后，完成分量、未读邻点及进入方向对应，后续可以继续逐块匹配。因此继续分支保留不差的完整答案。这个性质保留了“确实存在共同前缀继续分支”的前提，不能只因下一字符仍递增就换根。同轮多个结束根必相邻，否则它们的标签各落在对方左段中，会同时推出 $r<s$ 与 $s<r$；它们属于同一完成分量，续写相同。所以首个严格胜出的结束根可以返回。

续写。 每个左段来自一个父亲，倒扫 $W$ 能恢复记录链。父亲边保证暴露，记录链保证左段次序；它们与固定根合法日程相容且无环。就绪空任务提前执行无损，非空任务右首互异，取最小者就是首差最优选择。依次拼接右载荷得到固定根最优答案，再结合选根结论得到全局最优。

消元合并、完成分量更新均为线性次并查集操作；字符树、前沿与失配回放都是线性规模。排序、接入二分、路径压缩并查集及最小堆拓扑排序合计确定性 $O(n\log n)$ 时间，所有结构合计 $O(n)$ 空间。

同样的时间空间量纲，完整代码不到 100 行，2.6 KB。出题人出题的时候也没做完的题就是简单。

附录 3

对"GPT 話你知": Thoses tasks surpassed by LLMs 的拙劣模仿。

官方题解和你的 GPT 只能做到 $O(n\log n)$？玩的太差了。下面给出一个时间复杂度 $O(n)$、空间复杂度 $O(n)$ 的做法。先走到 $O(n\alpha(n))$，再把剩下的并查集因子逐项消掉。

题解

记 $N[u]$ 为闭邻域，$Q(u)$ 为其升序串，$b(u)=\min N[u]$。固定初始中心 $r$，每次将新儿子中小于串首的部分接到左侧，其余接到右侧，得到 $F(r)=L_s\cdots L_1Q(r)R_1\cdots R_s$。先提取递增短串 $W(r)=L_s\cdots L_1Q(r)$，再处理根块结束之后的右侧输出。

消元树共享全部短串

固定根的非空左段来自路径上严格刷新 $b$ 最小值的记录中心，记录按 $b$ 递减执行。按 $(b(u),u)$ 构造最小点删除的消元树：删去最小中心，再递归各分量。消元祖先链中的每段同权中心只保留最后一个，就是固定根的记录序列。

消元边 $u\to v$ 输出 $Q(u)$ 中小于 $b(v)$ 的前缀，终点 $r$ 再输出完整的 $Q(r)$。为每个中心建立一条邻域字符链，把各消元儿子接到相应前缀末尾，便能共享所有短串。字符总数为 $3n-2$，加一个虚根得到线性大小的字符树。

逐层取前沿后继的最小字符，并保留全部相同字符的后继，得到路径 $P$。短串终点交给后续比较，结束符不参与继续字符选择。再遍历字符树求每个根的首次失配时刻 ban，记录标签位置 id。

上述构造可以线性完成：邻表按整数标签转置排序，中心按 $b$ 入桶；逆序激活时收缩原树边，另存分量的消元根；按 $b$ 递增查询父链接入位置，每条父链只需一个单调游标。排序、截取和字符扫描都不需要比较数据结构。

首差变成窗口覆盖

闭邻域全部出现在 $P$ 的中心，在 $\tau(u)=\max\limits_{v\in N[u]}id[v]$ 时完成。该时刻仍匹配前缀，就恰好是合法短串结束根。逐轮激活完成中心，合并其原树相邻分量。

对第 $k$ 轮结束根所在分量 $C$，令 $t$ 为 $P_1,\ldots,P_k$ 中最后一个不在 $N[C]$ 的位置。根块读完并补空右段操作后，当前真实大串为 $P_{t+1}\cdots P_k$。比较结束分支是否严格小于下一继续字符 $P_{k+1}$，末轮取哨兵 $n+1$。

对已读中心 $u$，非零邻点位置为 $q_1<\cdots<q_d$，整条 $P$ 外最小邻点为 $a(u)$。定义 $g(u)=\min(\{id[u]\}\cup\{q_i+1:q_i+1<q_{i+1}\})$、$e(u)=\max(id[u],|\{i:P_i<a(u)\}|)$。不存在 $a(u)$ 就不贡献。中心合法且能给出严格更小字符，等价于 $e(u)\le k$ 且 $g(u)>t$，故预处理 $D_k=\max(\{0\}\cup\{g(u):e(u)\le k\})$ 即可。

严格胜出就是 $D_k>t$，也就是 $D_k>0$ 且窗口 $P_{D_k},\ldots,P_k$ 被 $N[C]$ 完全覆盖。维护静态后缀 $\{P_l,\ldots,P_M\}$ 的覆盖数，让 $l=\max(1,D_k)$ 单调右移。完成分量不含未来字符，所以静态后缀与当前窗口的交集相同。合并两个相邻分量时，闭邻域只重复连接边两端，直接扣重。

下一字符较大的结束分支落败；相等时，存在匹配的继续短串，产生共同字符的完整块可以接管旧分支。首个严格胜出的结束根就是所需根，返回它及准确的 $W$。若 $P$ 长度已为 $n$，直接输出。

从比较堆到有效父亲树

重定根后，各中心未出现在 $W$ 中的儿子构成右载荷，非空右首互异，记为 $a(u)$；空载荷记零。倒扫 $W$ 的父亲连续段，恢复记录链。任务图由原父亲边与记录链边组成，目标是最小关键码拓扑序。

数学上给任务赋权 $2^{a(u)}$，空任务为零，令 $V(u)$ 为终点为 $u$ 的最大路径权。按 $V$ 排列非空任务，恰好就是最小就绪序。实现只需要在每个记录点的原父亲和上一记录之间，选出 $V$ 更大的前驱，形成一棵有效父亲树。

按记录链加入每个新记录的原树祖先新路径。所有旧点都能到达上一记录，故其数值不超过上一记录的 $M$。若基点与 $M$ 的最高不同位为 $d$，新路径中记录点之前的最大关键码为 $H$，则原父亲比上一记录大当且仅当 $H>d$，由此决定有效父亲。

只保存每点的出生首差，以及随后每轮最大记录变化的最高不同位 $q_j$。因为 $A\le B\le C$ 时 $\delta(A,C)=\max(\delta(A,B),\delta(B,C))$，旧点当前首差就是出生首差与出生后全部 $q_j$ 的最大值。新路径各点只加入一次，每轮的出生首差通过新路径的前缀或后缀最大值线性算出，剩下一个追加式后缀最大值接口。

有效树上，沿根路径维护递减栈：读入关键码时弹掉较小尾部，再追加它，得到截尾签名。每个非空点的签名父亲是最近的严格更大关键码祖先。先删空点，再按关键码递增删除，用最近未删除祖先查询得到所有签名父亲。签名孩子按关键码排序，前序遍历就是最优任务序，依次输出右载荷即可。

先到反阿克曼，再到线性

消元分量、完成分量、最近更大祖先以及单调后缀最大值，都只需线性次集合操作。用按大小合并加路径压缩，语义名字另外保存，得到 $O(n\alpha(n))$ 时间、$O(n)$ 空间。

前三个树分量问题都能进一步用固定树合并：消元与完成过程收缩的是已知原树边，最近更大祖先收缩的是已经完整求出的有效父亲树边。增加永久保留的虚根零，收缩 $(u,p(u))$ 等价于删除 $u$ 的标记，查分量就是找最近保留祖先。

取微块大小 $\Theta(\log n)$，每块加上唯一外部入口后连通，用一个字保存块内祖先集合和保留点集合。按位与后取最高位，得到块内最近保留祖先；不存在就跳到外部入口。

只有 $O(n/\log n)$ 个外部入口参与宏集合。宏集合用成员直接编号查询，合并时小集合全体改名，并保存祖先侧语义名字。每次跨块循环会合并两个不同宏集合，每个宏成员至多改名 $O(\log n)$ 次，所以全部改名量为 $O((n/\log n)\log n)=O(n)$。线性次查找与删除的总费用也是 $O(n)$。

后缀最大值单独改成追加式分块 RMQ。块长取 $\Theta(\log n)$，块内递减栈用位掩码，整块最大值建稀疏表。只有 $O(n/\log n)$ 个整块，全部表项和构建时间都是 $O(n)$。每次后缀查询由两端的部分块和中间完整块组成，常数时间回答。

正确性与复杂度

短串表示。 固定根规范扩展与独立左目标的交换给出记录次序。消元祖先性质来自原路径最小值；同权中心都邻接同一最小标签，使祖先链只需保留最后一个同权点。对消元边 $u\to v$，朝根的原邻点 $p$ 满足 $b(v)\le b(p)\le\min(u,p)$，因此截取部分恰为左段，不含旧字符。共享字符链保留全部终点路径，前沿逐层保留全部最小字符分支，故 $P$ 与失配时刻精确。

选根。 完成时刻与前缀匹配条件准确识别根块结束。树上唯一路径保证补空操作后，真实大串由完成分量的最后覆盖缺口确定。邻点断档与未读最小字符给出 $g,e$，所以 $D_k>t$ 精确等价于严格胜出，闭邻域扣重又精确实现窗口覆盖。相等接管要求存在实际继续分支；连续处理共同块后两边的未读块及入口对应，能保留不差的完整答案。同轮结束根必相邻、属于同一完成分量，续写相同。因此首个严格胜出的结束根可以返回。

数值排序。 最大路径权沿非空依赖严格增加，所以数值序是拓扑序。若当前最小数值任务为 $v$，却有关键码更小的就绪 $u$，则 $u$ 的最大前驱路径不含 $v$，与 $V(v)$ 的最高首差至少在 $a(v)$。加入更低的 $a(u)$ 不改变首差，仍得到 $V(u)<V(v)$，矛盾。空任务通过只传递依赖的逻辑收缩处理。

有效父亲。 上一记录支配全部旧点，新路径关键码未在旧路径出现，故 $H>d$ 精确判断哪个前驱更大。单调三点首差公式精确维护后续比较。沿原 DAG 拓扑序归纳，有效树保留每个点的最大路径值，因此保留最优任务次序。

签名排序。 截尾追加总使签名严格增大，保证祖先先于后代。若 $A<B$，$B$ 末项为 $b$，且新关键码 $a<b$，则截尾追加后的 $F_a(A)<B$，共同前缀不会被截掉，首差方向不变。这排除了“还存在更小的就绪任务”，故签名序也是最小就绪序。最近更大祖先正好给出签名前缀，用签名树前序得到完整最优续写。

所有字符链、任务、记录新路径、阈值贡献及边操作都只有线性多个。三处固定树合并采用微块加宏集合的小并大改名，总时间线性；追加式 RMQ 的总构建线性、每次查询常数。所有排序均为整数桶或已有有序邻表扫描。因此算法部分达到确定性 $O(n)$ 时间、$O(n)$ 字空间。

这里采用竞赛中对整数和 $\Theta(\log n)$ 位机器字操作的计费方式；十进制文本读写另外按实际字符长度计费。线性并查集的界是整段操作序列的摊还总界，不要求单次查找最坏常数。

附录 2：你跑不过我你信吗？