C - Dyed by Majority (Odd Tree) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点の木が与えられます． 頂点には 1 から N までの番号が付いており，i 番目の辺は頂点 A_i と頂点 B_i を結んでいます． また，すべての頂点について，接続する辺の本数は奇数です．

与えられた木の各頂点を黒 ( B ) か白 ( W ) のいずれかの色で塗ります． このとき，「各頂点の色（ B または W ）を頂点の番号順に並べて得られる文字列」を色の列と呼びます．

色の列 S が与えられます． すべての頂点に色が塗られた状態で以下の操作を 1 回行った結果，色の列が S となることがあり得るかどうかを判定し，あり得るなら操作を行う前の色の列として適切なものを 1 つ求めてください．

操作: 各頂点 k = 1, 2, \dots, N に対して，辺で結ばれた頂点の色のうち過半数を占めるものを C_k とする． すべての頂点について同時に，頂点 k の色を C_k に塗り替える．

T 個のテストケースが与えられるので，それぞれについて答えてください．

制約

  • T \geq 1
  • N \geq 2
  • 1 つの入力に含まれるテストケースについて，N の総和は 2 \times 10^5 以下である．
  • 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq N - 1)
  • 与えられる辺 (A_i, B_i) \ (1 \leq i \leq N - 1) は木をなす．
  • 各頂点 k \ (1 \leq k \leq N) は A_i, B_i \ (1 \leq i \leq N - 1) として合計奇数回現れる．
  • S は B, W からなる長さ N の文字列である．

入力

入力は以下の形式で標準入力から与えられる．

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

各テストケース \mathrm{case}_i \ (1 \leq i \leq T) は以下の形式である．

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
S

出力

T 行出力せよ． i 行目には，i 番目のテストケースについて，操作の結果として色の列が S となることがあり得るなら操作を行う前の色の列として適切なものを，あり得ないなら -1 を出力せよ． 操作を行う前の色の列として適切なものが複数存在する場合，そのような色の列のうちどれを出力しても正答と見なされる．

入力例 1

2
4
1 2
1 3
1 4
BWWW
4
1 2
1 3
1 4
BBWW

出力例 1

WBBW
-1

1 つ目のテストケースについて，操作を行う前の色の列が WBBW であったとします． このとき，

  • 頂点 1 について，辺で結ばれた頂点 2, 3, 4 の色はそれぞれ B, B, W であり，過半数を占めるのは C_1 = {}B，
  • 頂点 2 について，辺で結ばれた頂点 1 の色は W であり，過半数を占めるのは C_2 = {}W，
  • 頂点 3 について，辺で結ばれた頂点 1 の色は W であり，過半数を占めるのは C_3 = {}W，
  • 頂点 4 について，辺で結ばれた頂点 1 の色は W であり，過半数を占めるのは C_4 = {}W となります．

したがって，操作後の色の列は BWWW となり，条件を満たします． 同様に，操作前の色の列が WBBB, WBWB, WWBB であった場合にも，操作後の色の列は BWWW となり，これらのうちどれを出力しても正答と見なされます。

2 つ目のテストケースについて，入力された木において操作を行った結果，色の列が BBWW となることはあり得ません．

Score : 500 points

Problem Statement

You are given a tree with N vertices. The vertices are labeled from 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Moreover, for every vertex, the number of incident edges is odd.

You will color each vertex of the given tree either black ( B ) or white ( W ). Here, the string obtained by arranging the colors ( B or W ) of the vertices in the order of vertex labels is called a color sequence.

You are given a color sequence S. Determine whether the color sequence S can result from performing the following operation once when all vertices are colored, and if it can, find one possible color sequence before the operation.

Operation: For each vertex k = 1, 2, \dots, N, let C_k be the color that occupies the majority (more than half) of the colors of the vertices connected to k by an edge. For every vertex k, change its color to C_k simultaneously.

There are T test cases to solve.

Constraints

  • T \geq 1
  • N \geq 2
  • The sum of N over the test cases in each input file is at most 2 \times 10^5.
  • 1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq N - 1)
  • The given edges (A_i, B_i) \ (1 \leq i \leq N - 1) form a tree.
  • Each vertex k \ (1 \leq k \leq N) appears an odd number of times in total as A_i, B_i \ (1 \leq i \leq N - 1).
  • S is a string of length N consisting of B and W.

Input

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

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

Each test case \mathrm{case}_i \ (1 \leq i \leq T) is in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
S

Output

Print T lines. For the i-th line, if the color sequence S can result from performing the operation in the i-th test case, print one possible color sequence before the operation; otherwise, print -1. If there are multiple possible color sequences before the operation, any of them will be considered correct.

Sample Input 1

2
4
1 2
1 3
1 4
BWWW
4
1 2
1 3
1 4
BBWW

Sample Output 1

WBBW
-1

For the first test case, suppose the color sequence before the operation was WBBW. In this case,

  • for vertex 1, the colors of the connected vertices 2, 3, 4 are B, B, W, respectively, with C_1 = {}B occupying the majority;
  • for vertex 2, the color of the connected vertex 1 is W, with C_2 = {}W occupying the majority;
  • for vertex 3, the color of the connected vertex 1 is W, with C_3 = {}W occupying the majority;
  • for vertex 4, the color of the connected vertex 1 is W, with C_4 = {}W occupying the majority.

Therefore, the color sequence after the operation is BWWW, satisfying the condition. Similarly, if the color sequence before the operation was WBBB, WBWB, or WWBB, the color sequence after the operation would be BWWW, and any of these are considered correct.

For the second test case, the color sequence BBWW cannot result from the operation on the given tree.