本文共 1140 字，大约阅读时间需要 3 分钟。

最后构造的树一定可以分为若干段连续的长度为$2$的连通块

连通块内的颜色相同

容易想到叶子节点一定是和父节点同色的

那么我们可以$dfs$

如果这个节点分了组,跳过

如果没分组,让他和父亲在一个组(只能这么做)

这样实际上我们每次都是在给叶子节点和它的父节点分组

同组内的颜色相同,于是就可以染色了

#include 
   
    using namespace std;const int maxn = 3e5+10;struct edge{
   	int u,to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
    d[++cnt] = (edge){
   u,v,head[u]},head[u] = cnt; }int ok[maxn],id,col[maxn],n,flag = 1;vector
    
     vec[maxn];void dfs(int u,int fa){
   	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( v==fa )	continue;		dfs(v,u);	}	if( ok[u] )	return;	if( ok[u]==0&&ok[fa]==0&&i!=1 )	ok[u] = ok[fa] = ++id;//分组 	else	flag = 0;} void ran(int u,int fa){
   	col[u] = col[fa]^1;	for(auto v:vec[u] )	{
   		if( v==fa )	continue;		ran(v,u);	}}signed main(){
   	cin >> n;	for(int i=1;i
     
      > l >> r;		add(l,r); add(r,l);	}	dfs(1,0);	if( flag==0 ){
    cout << "-1"; return 0; }	for(int i=2;i<=cnt;i+=2)	{
   		int u = d[i].to, v = d[i].to;		if( ok[u]==ok[v] )	continue;		vec[ok[u]].push_back(ok[v]);		vec[ok[v]].push_back(ok[u]);	}	ran(1,0);	for(int i=1;i<=n;i++)	{
   		if( col[ok[i]]==0 )	cout << "R";		else	cout << "B";	}}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113576986 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！