红和蓝

思路

• 由每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点可得，如果叶子结点为一种颜色时，它的周围只有其父亲结点，所以父亲结点和它同色。

• 根据上述我们可以进行dfs，从下到上两两配对，存在一个没有与之配对的结点说明不存在此解

• 配对完成后在进行一遍dfs经行染色，如果是匹配的染同一颜色，否则染不同颜色。

代码

// Problem: 红和蓝
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9981/C
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int col[N];
int f[N];
vector<int> g[N];

void dfs1(int u,int fa){
    for(int v:g[u]){
        if(v==fa) continue;
        dfs1(v,u);
        if(!f[u]&&!f[v]){
            f[u]=v;
            f[v]=u;
        }
    }
}

void dfs2(int u,int fa){
    for(int v:g[u]){
        if(v==fa) continue;
        if(f[u]==v) col[v]=col[u];
        else col[v]=col[u]^1;
        dfs2(v,u);
    }
}

void solve(){
    int n;cin>>n;
    rep(i,1,n-1){
        int u,v;cin>>u>>v;
        g[u].pb(v);g[v].pb(u);
    }
    dfs1(1,0);
    rep(i,1,n){
        if(!f[i]){
            cout<<"-1\n";
            return;
        }
    }
    col[1]=1;
    dfs2(1,0);
    rep(i,1,n){
        if(col[i]) cout<<"R";
        else cout<<"B";
    }
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}