s02261. CSP-S 2019 复赛 D1T3 树上的数

题目描述

时间限制：2s　内存限制：256MB　来源：洛谷 P5659

题目描述

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

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

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

如上图，蓝圈中的数字 $1 \sim 5$ 一开始分别在结点②、①、③、⑤、④。按照 (1)(4)(3)(2) 的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为①③④②⑤，该排列是所有可能的结果中字典序最小的。

输入格式

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

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

对于每组测试数据：

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

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

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

输出格式

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

样例

输入

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

输出

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

说明/提示

【数据范围】

测试点编号	$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$ ，保证给出的是一个树。

s02261. CSP-S 2019 复赛 D1T3 树上的数 未做

题目描述

题目描述

输入格式

输出格式

样例

说明/提示

s02261. CSP-S 2019 复赛 D1T3 树上的数未做