题目的主要信息：

• 一棵无向树，给每个顶点染成红色或蓝色
• 每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点
• 无法完成染色输出-1，完成染色输出每个结点的颜色

具体做法：

首先叶子结点因为只与父亲结点相连，所以叶子结点与父亲结点同色，因此我们可以利用dfs从根节点开始递归遍历树，从叶子结点开始检测染色，将叶子结点与父结点染成同色，然后往上，如果遇到两个相邻结点都没有颜色，就染成同一色，否则不染色，这里我们可以用dp数组连上结点号表示。

遍历dp数组，如果每个结点都有颜色（即dp数组中都有值不为0），说明能够染色，否则就是不可以成功染色。

最后再次dfs，起点染色为红色，数组元素设置为1，遇到dp数组中相邻相同的点就染成相同的颜色，否则就设置为另一色（蓝色数组元素设置为0）

#include<iostream>
#include<vector>
using namespace std;

vector<int> G[100001];
int dp[100001];
int color[100010];

void dfs1(int cur, int pre){
    for(int i = 0; i < G[cur].size(); i++){ //遍历所有子节点
        int next = G[cur][i];
        if(next == pre) //不能进入父节点
            continue;
        dfs1(next, cur); //进入子树
        if(!dp[cur] && !dp[next]){ //从叶子开始，叶子和父节点同色，依次往上
            dp[cur] = next;
            dp[next] = cur;
        }
    }
}

void dfs2(int cur, int pre){
    for(int i = 0; i < G[cur].size(); i++){
        int next = G[cur][i];
        if(next == pre) //不能进入父节点
            continue;
        color[next] = dp[cur] == next ? color[cur] : !color[cur]; //根据邻近的染色信息染色
        dfs2(next, cur);
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); //构建邻接表
        G[v].push_back(u);
    }
    dfs1(1, -1); //第一次dfs尝试能否完成染色
    for(int i = 1; i < n; i++){ //检查是否每个结点都有颜色
        if(dp[i] <= 0){
            cout << -1 << endl;
            return 0;
        }
    }
    color[1] = 1; //第一个结点先染红色
    dfs2(1, -1); //第二次dfs给每个节点确定颜色
    for(int i = 1; i <= n; i++) //根据每个结点的01值输出颜色
        cout << (color[i] ? 'R' : 'B'); 
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，两次dfs都是单独遍历整棵树每个结点
• 空间复杂度：$O(n)O(n)$，dp数组邻接表和染色数组大小都为$O(n)O(n)$