#P19008. 【CodeChef START263A】Consistentree (Construct)

【CodeChef START263A】Consistentree (Construct)

题目描述

给定一棵包含 NN 个顶点的树,顶点编号为 11 到 NN。顶点 vv 的权值 AvA_v 为 −1-1、00 或 11。

给每个顶点分配一个标签,要求 11 到 NN 中的每个整数恰好使用一次。若分配后每个顶点 vv 都满足对应的条件,就称这棵树为一致的。

  • Av=−1A_v=-1 时,vv 的标签小于它的每个相邻顶点的标签。
  • Av=1A_v=1 时,vv 的标签大于它的每个相邻顶点的标签。
  • Av=0A_v=0 时,vv 至少有一个相邻顶点的标签比它小,并且至少有一个相邻顶点的标签比它大。

判断给定的树是否一致。若一致,输出任意一种满足要求的标签分配。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对于每组测试用例,第一行包含一个整数 NN。第二行包含 NN 个以空格分隔的整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

接下来的 N−1N-1 行,每行包含两个以空格分隔的整数 u,vu,v,表示顶点 uu 与 vv 之间有一条边。

输出格式

每组测试用例输出一行。

  • 若无法满足要求,输出 −1-1。
  • 若可以满足要求,输出 NN 个以空格分隔的整数 P1,P2,…,PNP_1,P_2,\ldots,P_N,其中 PiP_i 为分配给顶点 ii 的标签。若有多种合法分配,输出任意一种即可。

数据范围

  • 1≤T≤1051\le T\le 10^5。
  • 2≤N≤2⋅1052\le N\le 2\cdot 10^5。
  • Ai∈{−1,0,1}A_i\in\{-1,0,1\}。
  • 1≤u,v≤N1\le u,v\le N,给出的边构成一棵树。
  • 所有测试用例的 NN 之和不超过 2⋅1052\cdot 10^5。

样例输入

5
2
0 1
1 2
4
-1 0 0 1
1 2
2 3
3 4
5
0 -1 1 -1 1
1 2
1 3
1 4
1 5
5
0 1 1 1 1
1 2
1 3
1 4
1 5
7
-1 1 -1 0 1 -1 1
1 2
2 3
2 4
4 5
4 6
3 7

样例输出

-1
1 2 3 4
3 1 4 2 5
-1
1 6 2 5 7 3 4

样例说明

第一组中,顶点 11 的权值为 00,但它只有一个相邻顶点,无法同时满足两种大小关系。

第三组的样例分配给顶点 11 的标签为 33。顶点 22 和 44 的标签小于 33,顶点 33 和 55 的标签大于 33。

第四组中,顶点 11 的所有相邻顶点的权值都为 11,所以它们的标签都必须大于顶点 11 的标签。这与顶点 11 的要求冲突。

CodeChef 原题 Consistentree (Construct)