翻转一个点会把它相邻的点全部翻转,因此先从叶子开始自下而上考虑。不难发现,如果这个叶子是白色,那么它一定比它的父亲先翻转(否则它就翻不了了);而对于黑色的叶子,它一定比它的父亲后翻转。经过一波操作,我们得到了所有叶子的父亲的颜色。此时就可以把它们当作叶子处理,因为那些还没被删的叶子暂时影响不了它们。
经过模拟我们得到了树根的颜色。显然如果此时树根是黑点就无解,否则就自上而下操作。
这样我们发现父子之间的操作顺序可以确定,并且它们是充要的。建出 DAG 后跑拓扑排序即可求出字典序最小的解。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, a[maxn], ind[maxn];
char s[maxn];
vector<int> G[maxn], T[maxn];
void dfs(int u, int fa) {
a[u] = (s[u] == 'W');
for (int v : G[u]) {
if (v == fa) {
continue;
}
dfs(v, u);
a[u] ^= a[v];
if (a[v]) {
T[v].pb(u);
++ind[u];
} else {
T[u].pb(v);
++ind[v];
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
scanf("%s", s + 1);
dfs(1, -1);
if (!a[1]) {
puts("-1");
return;
}
priority_queue< int, vector<int>, greater<int> > pq;
for (int i = 1; i <= n; ++i) {
if (!ind[i]) {
pq.push(i);
}
}
while (pq.size()) {
int u = pq.top();
pq.pop();
printf("%d ", u);
for (int v : T[u]) {
if (!(--ind[v])) {
pq.push(v);
}
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}