分数: 500 点
问题陈述
你得到了一棵树 N 顶点。 顶点标记为 1 to N,以及 i第一条边连接顶点 A_i 和顶点 B_i。 此外,对于每个顶点, 入射边数为奇数.
您将给定树的每个顶点着色为黑色( B )或白色( W )。
这里,通过排列颜色获得的字符串( B or W )按顶点标签顺序排列的顶点称为 颜色序列.
给你一个颜色序列 S。 判断颜色是否顺序 当所有顶点都着色时执行一次以下操作可以得到 S ,如果可以,则在操作之前找到一种可能的颜色序列。
操作: 对于每个顶点 k = 1, 2, \dots, N,让 C_k 是占据连接到的顶点颜色的大多数(超过一半)的颜色 k 的边缘。 对于每个顶点 k,将其颜色更改为 C_k 同时进行。
有 T 测试用例解决。
约束
- T \geq 1
- N \geq 2
- 总和 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) 出现 总共奇数次 as A_i, B_i \ (1 \leq i \leq N - 1).
- S 是一个长度为的字符串 N 组成
B和W.
输入
输入由标准输入按以下格式给出:
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第行,如果颜色顺序 S 可以通过在 i-第一个测试用例,在操作之前打印一种可能的颜色序列;否则,打印 -1。
如果操作前有多种可能的颜色序列,则其中任何一个都将被认为是正确的。
示例输入 1
2 4 1 2 1 3 1 4 BWWW 4 1 2 1 3 1 4 BBWW
示例输出 1
WBBW -1
对于第一个测试用例,假设操作前的颜色顺序为 WBBW。
在这种情况下,
- 对于顶点 1,连接顶点的颜色 2, 3, 4 是
B,B,W分别与 C_1 = {}B占据多数; - 对于顶点 2,连接顶点的颜色 1 is
W,与 C_2 = {}W占据多数; - 对于顶点 3,连接顶点的颜色 1 is
W,与 C_3 = {}W占据多数; - 对于顶点 4,连接顶点的颜色 1 is
W,与 C_4 = {}W占据大多数。
因此,运算后的颜色顺序为 BWWW,满足条件。
类似地,如果操作之前的颜色顺序是 WBBB, WBWB,或 WWBB,操作后的颜色顺序为 BWWW,其中任何一个都被认为是正确的。
对于第二个测试用例,颜色序列 BBWW 无法由对给定树的操作产生。