我的想法是首先把所有的点的度数求出来，然后扔到小根堆里面去。每次 pop 当前队里度数最小的点，然后对于这个点 $x$，与它连边的所有点 $y$ 中，如果已经染色了那么直接统计，如果没有染色，那就染成 $s_x$，然后如果染完色之后发现所有 $y$ 中与 $s_x$ 不同的颜色的个数 $\ge deg[x]/2+1$ 那就返回 -1，负责继续这个过程直到构造完整个序列为止。

但是 WA*10 了，想问一下这个思路假在哪了或者我自己写挂挂哪了。

code:

//C
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define pii pair<int,int>
#define mk make_pair
using namespace std;
const int maxn=2e5+10;
int in[maxn],col[maxn],cnt[maxn];
string ret;

basic_string<int>edge[maxn];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int work(int n)
{
	for(int i=1;i<n;i++)
	{
		int a,b;
		a=read();b=read();
		edge[a]+=b;
		edge[b]+=a;
		in[a]++;in[b]++;
	}
	string s;
	cin>>s;
	s='%'+s;
	priority_queue<pii>q;
	for(int i=1;i<=n;i++)
	{
		q.push(mk(-in[i],i));
	}
//	for(int i=1;i<=n;i++)cout<<in[i]<<" ";
//	cout<<'\n';
	while(!q.empty())
	{
		int deg=-q.top().first,now=q.top().second;
		q.pop();
		cnt[1]=0;cnt[2]=0;
		int flag=(s[now]=='B'?1:2);
		for(int nxt:edge[now])
		{
			if(col[nxt])cnt[col[nxt]]++;
			else col[nxt]=flag;
		}
		if(s[now]=='B')
		{
			if(cnt[2]>=deg/2+1)return -1;
		}
		else if(s[now]=='W')
		{
			if(cnt[1]>=deg/2+1)return -1;
		}
	}
	ret="";
	for(int i=1;i<=n;i++)
	{
		if(col[i]==1)ret+='B';
		else ret+='W';
	}
	return 1;
}

int main()
{
	int T=read();
	while(T--)
	{
		int n=read();
		for(int i=1;i<=n;i++)edge[i].clear(),in[i]=0,col[i]=0;
		if(work(n)==-1)cout<<-1<<'\n';
		else cout<<ret<<'\n';
	}
}