分数: 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.
- 让 L 是以下长度中较小的一个 S 和 T。对于每个 i=1,2,\dots,L,我们检查是否 S_i 和 T_i 是相同的。
- 如果有 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 然后退出。
- 如果没有 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
在这种情况下,您根本无法执行该操作。