← 返回题目列表

AtCoder · arc143_e

E. 黑白棋

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

分数: 700 点

问题陈述

我们有一棵树 N 顶点。 顶点已编号 1 to N, 和 i第一条边连接顶点 A_i 和顶点 B_i。 此外,每个顶点上都有一个反转棋子。 每个顶点上的棋子的状态由一个字符串给出 S: 如果 i- 第一个字符 S is B,Vertex 上的部分 i 黑色面朝上放置; 如果 i- 第一个字符 S is W,Vertex 上的部分 i 白色面朝上放置。

判断是否可以执行以下操作 N 次从所有顶点移除碎片。 如果可能的话,找到字典顺序上最小的可能序列 P_1, P_2, \ldots, P_N 使得顶点 在此过程中可以按此顺序选择 P_1, P_2, \ldots, P_N 。

  • 选择一个包含白色面朝上的棋子的顶点,并将该棋子从该顶点移除。 然后,翻转与该顶点相邻的顶点上的所有块。
黑白棋的注释 黑白棋有黑面和白面,翻转它会改变哪一面朝上。
序列的字典顺序是什么?

以下是确定不同序列之间的字典顺序的算法 S 和 T.

下面,让 S_i 表示 i- 第一个元素 S。另外,如果 S 按字典顺序小于 T,我们将该事实表示为 S \lt T;如果 S 按字典顺序大于 T,我们将该事实表示为 S \gt T.

  1. 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
  2. 如果有 i 这样 S_i \neq T_i,让 j 是最小的这样 i。然后,我们比较 S_j 和 T_j。如果 S_j 小于 T_j (作为一个数字),我们确定 S \lt T 然后退出;如果 S_j 大于 T_j,我们确定 S \gt T 然后退出。
  3. 如果没有 i 这样 S_i \neq T_i,我们比较长度 S 和 T。如果 S 短于 T,我们确定 S \lt T 然后退出;如果 S 长于 T,我们确定 S \gt T 然后退出。

约束

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 给定的图是一棵树。
  • S 是一个长度为的字符串 N 由字符组成 B 和 W.

输入

输入由标准输入按以下格式给出:

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

输出

如果目标无法实现,请打印 -1。如果可以实现,请按以下格式打印答案:

P_1 P_2 \cdots P_N

样本输入 1

4
1 2
2 3
3 4
WBWW

示例输出 1

1 2 4 3 

示例输入 2

4
1 2
2 3
3 4
BBBB

示例输出 2

-1

在这种情况下,您根本无法执行该操作。