[CSP-S 2019] 树上的数

题目描述

给定一个大小为 $n$ 的树，它共有 $n$ 个结点与 $n - 1$ 条边，结点从 $1 \sim n$ 编号。初始时每个结点上都有一个 $1 \sim n$ 的数字，且每个 $1 \sim n$ 的数字都只在恰好一个结点上出现。

接下来你需要进行恰好 $n - 1$ 次删边操作，每次操作你需要选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。

$n - 1$ 次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字 $1 \sim n$ 所在的结点编号依次排列，就得到一个结点编号的排列 $P_i$。现在请你求出，在最优操作方案下能得到的字典序最小的 $P_i$。

例如，有一棵包含 $5$ 个结点的树，四条边依次编号为：边 $(1)$ 连接结点 $2,3$，边 $(2)$ 连接结点 $2,5$，边 $(3)$ 连接结点 $5,1$，边 $(4)$ 连接结点 $5,4$。数字 $1 \sim 5$ 一开始分别在结点 $2,1,3,5,4$ 上。

按照 $(1),(4),(3),(2)$ 的顺序删去所有边（每次删边前先交换该边两端结点上的数字）。操作完成后，数字 $1 \sim 5$ 分别位于结点 $1,3,4,2,5$，因此按数字顺序得到的结点编号排列为 $1,3,4,2,5$。该排列是所有可能结果中字典序最小的。

输入格式

本题输入包含多组测试数据。

第一行一个正整数 $T$，表示数据组数。

对于每组测试数据：

第一行一个整数 $n$，表示树的大小。

第二行 $n$ 个整数，第 $i (1 \leq i \leq n)$ 个整数表示数字 $i$ 初始时所在的结点编号。

接下来 $n - 1$ 行每行两个整数 $x$, $y$，表示一条连接 $x$ 号结点与 $y$ 号结点的边。

输出格式

对于每组测试数据，输出一行共 $n$ 个用空格隔开的整数，表示最优操作方案下所能得到的字典序最小的 $P_i$。

输入样例 #1

1
2
1 2
1 2

输出样例 #1

2 1

说明/提示

来源

洛谷原题 P5659

输入样例 #2

1
2
2 1
1 2

输出样例 #2

1 2

输入样例 #3

1
3
1 2 3
1 2
2 3

输出样例 #3

2 3 1

【数据范围】

测试点编号	$n \leq$	特殊性质
$1 \sim 2$	$10$	无
$3 \sim 4$	$160$	树的形态是一条链
$5 \sim 7$	$2000$	同上
$8 \sim 9$	$160$	存在度数为 $n - 1$ 的结点
$10 \sim 12$	$2000$	同上
$13 \sim 16$	$160$	无
$17 \sim 20$	$2000$

对于所有测试点：$1 \leq T \leq 10$，保证给出的是一个树。