AT_arc161_c.[ARC161C] Dyed by Majority (Odd Tree)

给定一棵有 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。此外，对于所有顶点，连接的边的数量都是奇数。

你需要用黑色（B）或白色（W）给每个顶点染色。此时，将“每个顶点的颜色（B 或 W）按顶点编号顺序排列得到的字符串”称为颜色序列。

给定一个颜色序列 $S$。请判断是否存在一种顶点染色方式，使得对所有顶点执行以下操作一次后，颜色序列变为 $S$。如果存在，请给出操作前的一种可能的颜色序列；如果不存在，输出 -1。

操作： 对每个顶点 $k=1,2,\dots,N$，令 $C_k$ 为与其通过边相连的顶点中占多数的颜色。然后，所有顶点同时将自己的颜色变为 $C_k$。

有 $T$ 组测试数据，请分别回答。

输入按以下格式从标准输入给出。

$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。

限制

• $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)$ 在所有 $A_i, B_i$ 中出现的次数总是奇数
• $S$ 是由 B 和 W 组成的长度为 $N$ 的字符串

样例解释 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。

由 ChatGPT 4.1 翻译