题解 | #红和蓝#

import java.util.*;

public class Main {
    private static class Node{
        List<Node> neighbor = new ArrayList<>();
        Node pair = null; // 树中的结点是两两组队的，这里记录它的队友
        char color = '_';
    }
    private static boolean abort = false;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node[] nodes = new Node[n+1];
        for(int i=1;i<=n;i++) nodes[i] = new Node();
        for(int i=1;i<n;i++) { // 记录邻接信息
            int l = sc.nextInt();
            int k = sc.nextInt();
            nodes[l].neighbor.add(nodes[k]);
            nodes[k].neighbor.add(nodes[l]);
        }
        getPairInfo(nodes[1],null); // 组队
        if(!abort && nodes[1].pair != null){
            paintColor(nodes[1],null);  // 染色
            for(int i=1;i<=n;i++) {
                System.out.print(nodes[i].color);
            }
        } else{
            System.out.print(-1);
        }
    }

    private static void getPairInfo(Node root,Node father){
        for(int i=0;i<root.neighbor.size();i++){
            Node cur = root.neighbor.get(i);
            if(cur == father) continue;
            getPairInfo(cur,root);// 先更新子节点
            if(abort) return; // 下层遍历如果发现无解则直接返回
            if(cur.pair == null){ // 子节点pair为空，说明子节点需要和当前节点组队
                if(root.pair != null){ // 子节点与当前节点组队发现此节点已经组队了，则无解，直接返回
                    abort = true;
                    return;
                }
                cur.pair = root;
                root.pair = cur;
            } // 如果子节点已经组队了，那么此节点应该与其父节点组队，直接返回即可，故else为空
        }
    }

    private static void paintColor(Node root,Node father){
        if(father != null && father.pair == root){
            root.color = father.color;
        } else {
            if(father != null) root.color = (father.color == 'B') ? 'R':'B';
            else root.color = 'B';
        }
        for(int i=0;i<root.neighbor.size();i++){
            Node cur = root.neighbor.get(i);
            if(cur == father) continue;
            paintColor(cur,root);
        }
    }
}

真不明白为什么这群写c++的，变量名也不好好取，也不写注释，代码可读性太差了

希望这篇回答会帮助正在尝试解题的你！