F - Avoid Division 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

N 頂点の木が与えられます。
頂点は頂点 1、頂点 2、\ldots、頂点 N と番号づけられており、i 番目 (1\leq i\leq N-1) の辺は頂点 U_i と頂点 V_i を結んでいます。

高橋君は各頂点を色 1、色 2、\ldots、色 K のうちいずれか一色で塗ります。
色 i は最大で C_i 個の頂点を塗るのに使うことができます。

次の条件をみたすように頂点を塗ることが可能か判定し、可能な場合は条件をみたす塗り方を 1 つ出力してください。

  • どの辺についても、ある i (1\leq i\leq K) が存在して、その辺で木を切って得られる 2 つの部分木の両方に色 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 を 1 つだけ出力せよ。
そうでないならば、N 個の整数 X_1,X_2,\ldots,X_N (1\leq X_i\leq K) を空白区切りで出力せよ。 ここで、j=1,2,\ldots,N について頂点 i を色 X_i で塗った方法が条件をみたすようにせよ。

入力例 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 個目のテストケースについて、出力例のように頂点を塗ったとします。
すなわち、頂点 1 に色 3 を、頂点 2 に色 2 を、頂点 3 に色 2 を、頂点 4 に色 1 を、頂点 5 に色 1 を塗ったとします。

このとき、頂点 1 と頂点 2 を結ぶ辺を切ったとすると、木は頂点 1,3 からなる部分木と頂点 2,4,5 からなる部分木に分かれますが、このときどちらにも色 2 で塗られた頂点（頂点 3 または頂点 2）が存在します。
与えられた木を他のどの辺で切ってもそのような色が存在するため、出力例の塗り方は条件をみたしています。

2 個目のテストケースについて、条件をみたすように頂点を塗る方法は存在しません。

Score : 550 points

Problem Statement

You are given a tree with N vertices.
The vertices are numbered vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq N-1) connects vertices U_i and V_i.

Takahashi will color each vertex with one of colors 1, 2, \ldots, K.
Color i can be used to color at most C_i vertices.

Determine whether it is possible to color the vertices satisfying the following condition, and if so, output one valid coloring.

  • For every edge, there exists some i (1\leq i\leq K) such that both of the two subtrees obtained by cutting the tree at that edge contain at least one vertex colored with color i.

You are given T test cases; solve each of them.

Constraints

  • 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
  • The given graph is a tree.
  • 1\leq C_i\leq N
  • C_1+C_2+\cdots+C_K\geq N
  • All input values are integers.
  • The sum of N over all test cases does not exceed 3\times 10^5.

Input

The input is given from Standard Input in the following format:

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

\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:

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

Output

Output T lines.
On the i-th line (1\leq i\leq T), output the answer for the i-th test case as follows.

If it is impossible to color the vertices satisfying the condition, output -1 alone.
Otherwise, output N integers X_1,X_2,\ldots,X_N (1\leq X_i\leq K) separated by spaces, such that coloring vertex i with color X_i for i=1,2,\ldots,N satisfies the condition.

Sample Input 1

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

Sample Output 1

3 2 2 1 1
-1

For the first test case, suppose the vertices are colored as in the sample output.
That is, vertex 1 is colored with color 3, vertex 2 with color 2, vertex 3 with color 2, vertex 4 with color 1, and vertex 5 with color 1.

If we cut the edge connecting vertices 1 and 2, the tree splits into the subtree consisting of vertices 1,3 and the subtree consisting of vertices 2,4,5; both subtrees contain a vertex colored with color 2 (vertex 3 or vertex 2, respectively).
Such a color exists no matter which edge of the given tree is cut, so the coloring in the sample output satisfies the condition.

For the second test case, there is no valid coloring satisfying the condition.