题解 | #红和蓝#

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
int e[N * 2], ne[N * 2], h[N], idx;
// sons[i] 记录节点i为根的子树的节点数
int sons[N];
// 记录节点的颜色
int colors[N];
bool isFailed = false;  // 是否染色失败
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
//递归的 求以cur为根的树 有多少个节点
int calcSon(int cur, int last){
    int sum = 1;
    for(int i = h[cur]; i != -1; i = ne[i]){
        // cur的孩子节点
        int ch = e[i];
        if(ch == last){  //防止向上递归（cur的孩子节点不能是它的父节点，虽然在遍历的时候cur和它父节点也存在边）
            continue;
        }
        sum += calcSon(ch, cur);
    }
    sons[cur] = sum;
    return sum;
}

void dfs(int t, int pt, int c){
    /*
    考虑每个节点i，
    1. 当i和par_i(i的父节点)颜色相同时，i 的所有儿子子树（以i的子节点c_i为根的子树）节点数为偶数，且所有子树根结点
    （i所有子节点）的颜色与节点i相反
    2. 当i和par_i(i的父节点)颜色 不相同 时，i 的所有儿子子树（以i的子节点c_i为根的子树）中必须有且仅有一个子树的节点数为奇数，
        其它子树的节点数都是偶数；且奇数节点数的子树根结点（i的某个子节点）的颜色与节点i相同，其它偶数节点数的子树根结点（i的除了奇数子树后所有的偶数子树的根节点）       的颜色与节点i  不相同
    */
    if(isFailed)
        return ;
    colors[t] = c;
    int cnt = 0;   
    for(int i = h[t]; i != -1; i=ne[i]){
        int ci = e[i];
        if(ci != pt){
            cnt += (sons[ci] & 1); // 判断节点i的所有子树 root-ci 中是否有且仅有一个奇数子树（子树节点个数奇数个） 
        }
    }
    //经过上面的循环，cnt=1表示节点t的 子树中 有且仅有一个奇数子树； cnt=0表示节点t的 子树中 全部为偶数子树
    if(colors[t] == colors[pt]){  //情况1，颜色相同
        if(cnt==1){  // 节点i的所有子树 root-ci 中 【有且仅有一个奇数子树】
            isFailed = true;
            return ;
        }
        for(int i = h[t]; i != -1; i=ne[i]){
            int child_i = e[i];
            if(child_i != pt){  //保证不向 上（父节点）递归，虽然他们之间也存在边
                dfs(child_i, t, c^1);  // t作为父节点， 它的所有儿子子树 节点数为偶数，且所有子树 根结点 的颜色与节点i相反（异或1）  
            }
        }
    }else{   //情况2，颜色 相反
        if(cnt!=1){   // 节点i的所有子树 root-ci 中 【不是 有且仅有一个奇数子树】
            isFailed = true;
            return ;
        }
        for(int i = h[t]; i != -1; i=ne[i]){
            int child_i = e[i];
            if(child_i != pt){
                if(sons[child_i] & 1){ // 是一个奇数子树时，t的孩子节点child_i 颜色和t相同
                    dfs(child_i, t, c);
                }else{
                    dfs(child_i, t, c^1);
                }
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n;
    int a, b;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    //以节点1作为整棵树的根节点。计算节点1的节点数
    sons[1] = calcSon(1,0);
    
    dfs(1,0,1);
    if(isFailed)
        printf("-1\n");
    else{
        for(int i = 1; i <=n;i++){
            if(colors[i])
                printf("B");
            else
                printf("R");
        }
    }   
    return 0;
}
// 64 位输出请用 printf("%lld")