首先能发现对于树的叶子节点，与其连边的只有其父节点，所以该节点最终状态为 \(\text{B/W}\) 其父节点的状态就一定为 \(\text{B/W}\)。
然后考虑它自己是什么状态，因为同样的与其连边的只有其父节点，所以其父节点最终状态为 \(\text{B/W}\) 其状态就为 \(\text{B/W}\)。
当一个节点的子节点都处理完状态后就该处理其和其父亲节点的状态，还是同样的方法，只不过因为这个点有子节点，其节点状态可能已经确定。
对于无解有 \(2\) 种情况：
- 父节点要同为 \(2\) 种状态才能满足子节点状态
- 父节点状态为 \(\text{B/W}\) 都无法满足子节点状态。
不难发现这其实就是一个拓扑的过程，从叶子节点一步步推到根节点。
时间复杂度 \(O(n)\)
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: C - Dyed by Majority (Odd Tree)
// Contest: AtCoder - AtCoder Regular Contest 161
// URL: https://atcoder.jp/contests/arc161/tasks/arc161_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int fa[N], d[N];
vector<int> G[N];
char s[N];
int c[N], col[N][2], ca[N];
int main() {
function<void ()> solve = []() -> void {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
G[i].clear(), d[i] = 0;
}
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
}
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
c[i] = (s[i] == 'B');
}
function<void (int)> dfs = [&dfs](int u) -> void {
for (int v : G[u]) {
if (v == fa[u]) {
continue;
}
fa[v] = u, d[u]++;
dfs(v);
}
};
dfs(1);
for (int i = 1; i <= n; i++) {
col[i][1] = col[i][0] = 1, ca[i] = 0;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (! d[i]) {
q.push(i);
}
}
for (; ! q.empty(); ) {
int u = q.front();
q.pop();
int v = fa[u];
if (c[u]) {
if (ca[u] > 0);
else if (ca[u] < 0) {
printf("-1\n");
return ;
}
else if (col[v][1]) {
col[v][0] = 0;
}
else {
printf("-1\n");
return ;
}
}
else {
if (ca[u] < 0);
else if (ca[u] > 0) {
printf("-1\n");
return ;
}
else if (col[v][0]) {
col[v][1] = 0;
}
else {
printf("-1\n");
return ;
}
}
if (col[u][0] + col[u][1] == 2) {
c[v] ? (col[u][0] = 0) : (col[u][1] = 0);
}
col[u][1] ? ca[v]++ : ca[v]--;
d[v]--;
if (! d[v]) {
q.push(v);
}
}
for (int i = 1; i <= n; i++) {
printf("%c", col[i][1] ? 'B' : 'W');
}
printf("\n");
};
int _;
scanf("%d", &_);
for (; _; _--) {
solve();
}
return 0;
}