题解 | 红和蓝

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, cnt = 0;
vector<int> g[N];
int f[N], col[N];  // f:配对关系, col:颜色
bool valid = true;

void dfs1(int x, int fa) {
    int son = 0;
    // 遍历所有子节点
    for(int y : g[x]) {
        if(y == fa) continue;
        son++;
        dfs1(y, x);
    }
    
    // 如果是叶子节点或未配对的节点
    if(son == 0 || f[x] == 0) {
        if(f[fa] != 0) {  // 如果父节点已配对，无解
            valid = false;
            return;
        }
        f[x] = f[fa] = ++cnt;  // 与父节点配对
    }
}

void dfs2(int x, int fa) {
    for(int y : g[x]) {
        if(y == fa) continue;
        // 根据配对关系染色
        col[y] = (f[y] == f[x]) ? col[x] : (col[x] ^ 1);
        dfs2(y, x);
    }
}

int main() {
    cin >> n;
    
    // 建图
    for(int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    dfs1(1, 0);
    
    // 检查是否有解
    if(f[0] != 0 || !valid) {
        cout << "-1" << endl;
        return 0;
    }
    
    // 从根节点开始染色
    col[1] = 1;
    dfs2(1, 0);
    
    // 输出结果
    for(int i = 1; i <= n; i++) {
        cout << (col[i] == 1 ? 'R' : 'B');
    }
    cout << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int N = 100010;
    static int n, cnt;
    static ArrayList<Integer>[] g;
    static int[] f;    // 配对关系
    static int[] col;  // 颜色
    static boolean valid = true;
    
    static void dfs1(int x, int fa) {
        int son = 0;
        // 遍历所有子节点
        for(int y : g[x]) {
            if(y == fa) continue;
            son++;
            dfs1(y, x);
        }
        
        // 如果是叶子节点或未配对的节点
        if(son == 0 || f[x] == 0) {
            if(f[fa] != 0) {  // 如果父节点已配对，无解
                valid = false;
                return;
            }
            f[x] = f[fa] = ++cnt;  // 与父节点配对
        }
    }
    
    static void dfs2(int x, int fa) {
        for(int y : g[x]) {
            if(y == fa) continue;
            // 根据配对关系染色
            col[y] = (f[y] == f[x]) ? col[x] : (col[x] ^ 1);
            dfs2(y, x);
        }
    }
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        // 初始化
        g = new ArrayList[N];
        for(int i = 0; i < N; i++) {
            g[i] = new ArrayList<>();
        }
        f = new int[N];
        col = new int[N];
        
        // 建图
        for(int i = 1; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            g[x].add(y);
            g[y].add(x);
        }
        
        dfs1(1, 0);
        
        // 检查是否有解
        if(f[0] != 0 || !valid) {
            System.out.println("-1");
            return;
        }
        
        // 从根节点开始染色
        col[1] = 1;
        dfs2(1, 0);
        
        // 输出结果
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++) {
            sb.append(col[i] == 1 ? 'R' : 'B');
        }
        System.out.println(sb.toString());
        
        sc.close();
    }
}

import sys
sys.setrecursionlimit(100010)

def dfs1(x, fa, g, f, cnt):
    son = 0
    # 遍历所有子节点
    for y in g[x]:
        if y == fa:
            continue
        son += 1
        dfs1(y, x, g, f, cnt)
    
    # 如果是叶子节点或未配对的节点
    if son == 0 or f[x] == 0:
        if f[fa] != 0:  # 如果父节点已配对，无解
            return False
        cnt[0] += 1
        f[x] = f[fa] = cnt[0]  # 与父节点配对
    return True

def dfs2(x, fa, g, f, col):
    for y in g[x]:
        if y == fa:
            continue
        # 根据配对关系染色
        col[y] = col[x] if f[y] == f[x] else (col[x] ^ 1)
        dfs2(y, x, g, f, col)

def main():
    n = int(input())
    
    # 建图
    g = [[] for _ in range(n+1)]
    for _ in range(n-1):
        x, y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    
    # 初始化
    f = [0] * (n+1)  # 配对关系
    col = [0] * (n+1)  # 颜色
    cnt = [0]  # 使用列表传递引用
    
    # 第一次DFS确定配对关系
    if not dfs1(1, 0, g, f, cnt) or f[0] != 0:
        print("-1")
        return
    
    # 从根节点开始染色
    col[1] = 1
    dfs2(1, 0, g, f, col)
    
    # 输出结果
    print(''.join('R' if c == 1 else 'B' for c in col[1:n+1]))

if __name__ == "__main__":
    main()