A108435.分裂晶体

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

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

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

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

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

请输出这条最稳定序列。

第一行一个整数 $n$。

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

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

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

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

数据范围与测试点分层

• $1\le n\le 2\times 10^5$
• $|a_i|\le 10^9$