atcoder#ARC143E. [ARC143E] Reversi

[ARC143E] Reversi

题目描述

N N 頂点からなる木があります. 各頂点には 1 1 から N N までの番号がついており, i i 番目の辺は頂点 Ai A_i と頂点 Bi B_i を結んでいます. また,各頂点にはリバーシの石が 1 1 つずつ置かれています. 各頂点に置かれている石の状態は文字列 S S によって与えられ, S S i i 番目の文字が B のとき,頂点 i i に置かれている石の表は黒色, S S i i 番目の文字が W のとき,頂点 i i に置かれている石の表は白色です.

以下の操作を N N 回行い,すべての頂点から石を取り除くことが可能かどうか判定してください. また可能ならば,列 P1,P2,,PN P_1,P_2,\ldots,P_N であって,頂点 P1,P2,,PN P_1,P_2,\ldots,P_N をこの順に選ぶことが可能なもののうち,辞書順で最小のものを求めてください.

  • 表が白色の石が置かれている頂点を 1 1 つ選び,その頂点から石を取り除く. そして,その頂点と隣接する頂点に置かれている石をすべて裏返す.

リバーシの石について リバーシの石は一方の面が黒色,もう一方の面が白色になっており,裏返すと表の色が入れ替わります. 数列の辞書順とは? 相異なる数列 S S と数列 T T の大小を判定するアルゴリズムを以下に説明します.

以下では S S i i 番目の要素を Si S_i のように表します.また, S S T T より辞書順で小さい場合は S < T S\ \lt\ T ,大きい場合は S > T S\ \gt\ T と表します.

  1. S S T T のうち長さが短い方の文字列の長さを L L とします.i=1,2,,L i=1,2,\dots,L に対して Si S_i Ti T_i が一致するか調べます.
  2. Si  Ti S_i\ \neq\ T_i である i i が存在する場合,そのような i i のうち最小のものを j j とします.そして,Sj S_j Tj T_j を比較して, Sj S_j Tj T_j より(数として)小さい場合は S < T S\ \lt\ T ,大きい場合は S > T S\ \gt\ T と決定して,アルゴリズムを終了します.
  3. Si  Ti S_i\ \neq\ T_i である i i が存在しない場合, S S T T の長さを比較して,S S T T より短い場合は S < T S\ \lt\ T ,長い場合は S > T S\ \gt\ T と決定して,アルゴリズムを終了します.

输入格式

入力は以下の形式で標準入力から与えられる.

N N A1 A_1 B1 B_1 \vdots AN1 A_{N-1} BN1 B_{N-1} S S

输出格式

目標が達成可能でない場合,-1 を出力せよ.可能である場合,以下の形式で答えを出力せよ.

P1 P_1 P2 P_2 \cdots PN P_N

题目大意

给定一棵树,以及每个节点上都有的一个翻转棋的初始状态,每次操作可以取走一枚白色朝上的棋子并将所有相邻的棋子翻转,求可以取走所有棋子的字典序最小的序列。

4
1 2
2 3
3 4
WBWW
1 2 4 3
4
1 2
2 3
3 4
BBBB
-1

提示

制約

  • 1  N  2× 105 1\ \leq\ N\ \leq\ 2\times\ 10^5
  • 1  Ai, Bi  N 1\ \leq\ A_i,\ B_i\ \leq\ N
  • 与えられるグラフは木である.
  • S S BW の文字からなる長さ N N の文字列である.

Sample Explanation 2

この場合,一度も操作を行うことができません.