← 返回题目列表

AtCoder · arc161_c

C. 多数染色(奇数树)

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

分数: 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 无法由对给定树的操作产生。