写的时候,每一步都要想好
不然就坐等调一天吧(
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
一道贪心,但是东挂一点西挂一点,做题就像挤牙膏,真的是很不好的状态!!
首先,考虑叶子结点,因为这是一棵树,那么他的父亲肯定是要满足他的
第一层关系出来了,同时第一种不满足关系也出来了:
如果叶子结点的父亲已经有了且和他不同,那么必定挂掉
然后往上考虑,对于每个节点,贪心的去向他的儿子们索求
有一种特殊情况:如果他的儿子的儿子们黑白个数相同,那么需要先向他索求
他就不能(也许)给他的父亲提供贡献了,
当然先考虑儿子
*/
const int N = 2*1e5+10;
int h[N],e[N*2],ne[N*2],f[N],cnt;
void add(int a,int b){
e[++cnt]=b;ne[cnt]=h[a];h[a]=cnt;
}
int T,n,a,b,ans[N],flag[N];
bool notye[N],wujie;
char s[N];
//1黑2白
void dfs(int u,int fa){
int cnt[3];cnt[0]=cnt[1]=cnt[2]=0;//记录u的儿子们的颜色数
if(wujie) return ;//无解直接退
f[u]=fa;//记录父亲,没用的
for(int i=h[u],v;i;i=ne[i]){//遍历
v=e[i];
if(v==fa) continue;
notye[u]=1;//记录是否是叶子结点
dfs(v,u);
if(ans[v]) cnt[ans[v]]++;//如果他的儿子有值了,那么那个值++
else ans[v]=flag[u],cnt[ans[v]]++;//否则将他儿子的值变为他的
}
if(!notye[u]){//如果他是叶子结点
if(ans[fa]!=0 && ans[fa]!=flag[u]) {//如果他的父亲有值了,还不是他
wujie=1;//无解
return ;
}
ans[fa]=flag[u];//否则将他父亲的值贡献给他,他的值贡献给他爸
ans[u]=flag[fa];
}
else if(cnt[1]==cnt[2]) {//如果u的儿子们黑白相等
if(ans[fa]!=0 && ans[fa]!=flag[u]) {//那么去找他的爸渴求,这个判断写错起码交了5次
wujie=1;return ;//如果矛盾无解
}
ans[fa]=flag[u];//渴求成功
}else if(cnt[flag[u]]<cnt[3-flag[u]]){//如果矛盾值大于了
wujie=1;//也是无解
return ;
}
return ;
}
int main()
{
scanf("%d",&T);
while(T--){
memset(h,0,sizeof(h));cnt=0;//全部初始化!!!
memset(notye,0,sizeof(notye));
memset(ans,0,sizeof(ans));
wujie=0;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
scanf("%s",s+1);
for(int i=1;i<=n;i++) {
flag[i]=(s[i]=='B'?1:2);//记到flag非s里,方便管理
}
dfs(1,0);
if(wujie) printf("-1\n");
else{
for(int i=1;i<=n;i++) {
printf("%c",ans[i]==1?'B':'W');
}
printf("\n");
}
}
return 0;
}