← 返回题目列表

AtCoder · abc453_f

I. 避免除法

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

你有一棵树 N 顶点。
顶点编号为顶点 1,顶点 2, \ldots,顶点 N,以及 i第边缘 (1\leq i\leq N-1) 连接顶点 U_i 和 V_i.

Takahashi 将使用其中一种颜色为每个顶点着色 1, 2, \ldots, K.
颜色 i 最多可用于着色 C_i 顶点。

判断是否可以对满足以下条件的顶点进行着色,如果可以,则输出一种有效的着色。

  • 对于每条边,都存在一些 i (1\leq i\leq K) 使得通过在该边切割树获得的两棵子树都包含至少一个用颜色着色的顶点 i.

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\leq T\leq 10^5
  • 2\leq N\leq 3\times 10^5
  • 1\leq K\leq N
  • 1\leq U_i,V_i\leq N
  • 给定的图是一棵树。
  • 1\leq C_i\leq N
  • C_1+C_2+\cdots+C_K\geq N
  • 所有输入值均为整数。
  • 总和 N 所有测试用例不超过 3\times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i 代表 i- 第一个测试用例。 每个测试用例均按以下格式给出:

N K
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
C_1 C_2 \ldots C_K

输出

输出 T 行。
关于 i第行 (1\leq i\leq T),输出答案 i第一个测试用例如下。

如果无法对满足条件的顶点着色,则输出 单独 -1 。
否则,输出 N 整数 X_1,X_2,\ldots,X_N (1\leq X_i\leq K) 用空格分隔,这样着色顶点 i 有颜色 X_i 为 i=1,2,\ldots,N 满足条件。


示例输入 1

2
5 3
1 2
1 3
2 4
2 5
2 2 2
3 3
1 2
2 3
1 1 1

示例输出 1

3 2 2 1 1
-1

对于第一个测试用例,假设顶点的颜色与示例输出中相同。
即顶点 1 是用颜色着色的 3,顶点 2 有颜色 2,顶点 3 有颜色 2,顶点 4 有颜色 1和顶点 5 有颜色 1.

如果我们切割连接顶点的边 1 和 2,树分裂成由顶点组成的子树 1,3 以及由顶点组成的子树 2,4,5;两个子树都包含一个用颜色着色的顶点 2 (顶点 3 或顶点 分别为 2)。
无论给定树的哪条边被切割,这种颜色都存在,因此样本输出中的颜色满足条件。

对于第二个测试用例,没有满足条件的有效着色。