← 返回比赛

已结束贝加尔国际运算编程大赛校内选拔赛(公开赛)

← 上一题下一题 →

A4590 | $书架$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

时间限制:1000ms 空间限制:512mb 小 X 的书架上总是堆满了书。 但是这些书摆放的乱的要命。 一开始，小 X 的书架上，$n$本书从左到右依次摆放，第$i$本书的编号是$a_i$，保证所有的$a_i$构成了一个$1$~$n$的排列。 现在，小 X 决定整理这些书。 整理这些书的策略分为$n-1$步，每一步有两个参数$x,y$。 表示的是：将 第$x$本书 所在的那一列，和 第$y$本书 所在的那一列， 穿插合并 。保证每次$x$与$y$不在同一列。 穿插合并 的规则是：依次在两列书中从上到下选择一本插s入新的列中，如果某一列书没有了，就把剩下的书按顺序插入。 例如： 例如：$$[1,2,3,4,5,6],[7,8,9]=>[1,7,2,8,3,9,4,5,6]$$ 现在，给定小 X $n-1$步穿插操作的流程，且保证已经将所有书合成了一列。现在，请你输出这$n$本书从上到下的 编号 。

输入格式

第一行输入一个正整数$n$，表示书的个数。 接下来一行$n$个正整数，表示$a_1,...,a_n$，保证这是一个$1$~$n$的排列。 接下来$n-1$行，每行两个正整数$x,y$，表示合并了第$x$本书当前所在的堆以及第$y$本书当前所在的堆。

输出格式

输出仅一个数字，表示最终的排列$b_1$~$b_n$的每个数字，$b_1*1+b_2*2+b_3*3+...+b_n*n$的结果。

输入输出样例

输入 #1

输出 #1

输入 #2

10
1 2 3 4 5 6 7 8 9 10
1 2
1 3
1 4
1 5
6 7
6 8
6 9
6 10
1 10

输出 #2

C++ 编辑器

输入

输出