#P17927. Memory, Permutation, and Rooted Tree

Memory, Permutation, and Rooted Tree

Memory, Permutation, and Rooted Tree

题目描述

给定一棵有 nn 个顶点、以顶点 11 为根的树。

对于顶点编号的一个排列 p1,…,pnp_1,\ldots,p_n,若顶点 vv 是 uu 的严格后代,且 vv 在排列中出现在 uu 之前,则称 vv 对 uu 是重要的。

定义 dud_u 为 uu 到所有对它重要的顶点的最小距离。若不存在这样的顶点,则 du=−1d_u=-1。树上距离指简单路径的边数。

现在给出树和数组 d1,…,dnd_1,\ldots,d_n,请恢复能产生这个数组的字典序最小的排列;若不存在,则报告无解。

两个不同排列在第一个不同位置上,数字较小的排列字典序较小。

输入格式

第一行一个整数 TT,表示测试数据组数。每组数据:

第一行一个整数 nn。

第二行 nn 个整数 d1,…,dnd_1,\ldots,d_n。

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

输出格式

每组数据输出一行。若有解,输出字典序最小的排列;否则输出 -1。

数据范围

  • 1≤T≤5×1041\le T\le5\times10^4,2≤n≤5×1052\le n\le5\times10^5。
  • −1≤di≤n-1\le d_i\le n。输入允许 di=0d_i=0,不保证有解。
  • 1≤u,v≤n1\le u,v\le n,u≠vu\ne v,输入的边构成一棵树。
  • 所有测试数据的 nn 之和不超过 5×1055\times10^5。

样例

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