← 返回比赛
已结束 GESP巅峰赛#32
← 上一题 下一题 →

A7304 | 分裂晶体

时间限制2s
内存限制512MB
通过 / 提交0/0

题目描述

雾港学宫研究一种“分裂晶体”。一块晶体会分裂成若干子晶体，每个子晶体又会继续分裂……最终形成一棵以 1 号晶核为根的树。

每个晶体节点 $i$ 有一个能量值 $a_i$（整数）。学宫用先序遍历（preorder）读取整棵晶体的能量序列：

- 先读取当前节点；
- 再按某个顺序依次读取它的每个子树。

由于晶体结构可塑，在读取之前，你可以对每个节点的子晶体做任意重排（也就是任意改变该节点孩子的顺序）。

定义所有可重排方案中得到的先序能量序列里，字典序最小的那个为“最稳定序列”。

请输出这条最稳定序列。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

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

保证输入是一棵树，且以节点 1 为根进行先序遍历。

输出格式

输出一行 $n$ 个整数，表示最稳定序列（字典序最小的先序遍历能量序列）。

输入输出样例

输入 #1
7
5 1 1 9 2 2 3
1 2
1 3
2 4
2 5
3 6
3 7
输出 #1
5 1 2 3 1 2 9
C++ 编辑器
输入
输出