红和蓝

难度：4星

可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：

• 若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。

• 若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同，其他都和x不同。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[200020];
int dp[200020];
int su(int x,int pr){
    int i,sum=1;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            sum+=su(g[x][i],x);
        }
    }
    return dp[x]=sum;
}
char out[200020];
int jud=0;
char f(char c){
    if(c=='R')return 'B';
    return 'R';
}
void dfs(int x,int pr,char c){
    if(jud)return;
    out[x]=c;
    int cnt=0,i;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            cnt+=dp[g[x][i]]&1;
        }
    }
    if(out[x]==out[pr]){
        if(cnt!=0){jud=1;return;}
        for(i=0;i<g[x].size();i++){
            if(g[x][i]!=pr){
                dfs(g[x][i],x,f(c));
            }
        }
    }
    else {
        if(cnt!=1){jud=1;return;}
        for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            if(dp[g[x][i]]&1)dfs(g[x][i],x,c);
                else dfs(g[x][i],x,f(c));
            }
        }
    }
}
int main(){
    int n,i;
    cin>>n;
    for(i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp[1]=su(1,-1);
    out[0]='B';
    dfs(1,0,'R');
    if(jud)cout<<-1;
    else for(i=1;i<=n;i++)cout<<out[i];
}