题目思路

容易想到叶子节点一定要涂成蓝色，因为以叶节点为根的子树只有一个点，而0是偶数，以此类推就所有点都唯一确定。

采用深度优先搜索实现，更新当前点的所有子节点后用子节点中蓝色节点的个数来确定当前点应该是什么颜色，如果子节点中有偶数个蓝色点，则当前点为蓝色点，反之为红色。

代码

Python代码

import sys
sys.setrecursionlimit(300000)	#深度优先搜索要求栈空间大一点
n = int(input())
e = [[] for i in range(n+1)]
for i in range(1, n):
	x, y = map(int,input().split())
	e[x].append(y)		#双向建边
	e[y].append(x)

ans = [0]*(n+1)		#记录答案
def dfs(s, fr):	#s代表当前点，fr代表当前点的父节点
	global ans	#引用全局变量
	sum = 0		#记录返回值
	for i in e[s]:
		if i != fr:		#跳过父节点避免死循环
			sum += dfs(i, s)
	if sum%2 == 0:	#如果当前的子树中有偶数个蓝色节点，将当前节点图成蓝色
		ans[s] = 1
		return sum+1
	else:			#反之图成红色,即不染色
		ans[s] = -1
		return sum

dfs(1, 0)	#从根节点开始深度优先搜索

for i in range(1, n+1):		#输出答案
	if ans[i] == 1:
		print("B", end = '')
	else:
		print("R", end = '')

C++代码

#include <iostream>
#include <vector>
using namespace std;
const int maxn=1e5+10;
vector<int>G[maxn];
int ans[maxn];
int n;
int dfs(int u,int fa){//u代表当前点，fa代表当前点的父节点
	int sum=0;	//记录返回值
	for (int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if (v==fa)	//跳过父节点避免死循环
			continue;
		sum+=dfs(v,u);
	}
	if (sum%2==0)	//如果当前的子树中有偶数个蓝色节点，将当前节点图成蓝色
	{
		ans[u]=1;
		return sum+1;
	}
	else 	//反之图成红色,即不染色
		return sum;
}
int main()
{
	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);
	}
	dfs(1,0);
	for (int i=1;i<=n;i++)
	{
		if (ans[i]==1)
			cout<<"B";
		else
			cout<<"R";
	}
	return 0;
}

Java代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {
    public static List<Integer>[] G;
    public static int[] ans;

    public static int dfs(int u, int fa) {// u代表当前点，fa代表当前点的父节点
        int sum = 0; // 记录返回值
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u].get(i);
            if (v == fa) // 跳过父节点避免死循环
                continue;
            sum += dfs(v, u);
        }
        if (sum % 2 == 0) // 如果当前的子树中有偶数个蓝色节点，将当前节点图成蓝色
        {
            ans[u] = 1;
            return sum + 1;
        } else // 反之图成红色,即不染色
            return sum;
    }

    public static void main(String[] args) {
        int n;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        G = new ArrayList[n + 1];
        ans = new int[n + 1];
        for (int i = 1; i <= n; i++)
            G[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            G[u].add(v); // 双向建边
            G[v].add(u);
        }
        dfs(1, 0);
        for (int i = 1; i <= n; i++) {
            if (ans[i] == 1)
                System.out.print("B");
            else
                System.out.print("R");
        }
    }
}

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
  input += data;
  return;
});
process.stdin.on('end', () => {
    var inputarray=input.split('\n');
    var n=Number(inputarray[0]);
    var G=[];
    var ans=[];
    for (let i=1;i<=n;i++)
        G[i]=[];
    for (let i=1;i<n;i++){
        let u,v;
        u=Number(inputarray[i].split(' ')[0]);
        v=Number(inputarray[i].split(' ')[1]);
        G[u].push(v);
        G[v].push(u);
    }
    function dfs(u,fa){//u代表当前点，fa代表当前点的父节点
        let sum=0;	//记录返回值
        for (let i=0;i<G[u].length;i++){
            let v=G[u][i];
            if (v==fa)	//跳过父节点避免死循环
                continue;
            sum+=dfs(v,u);
        }
        if (sum%2==0)	//如果当前的子树中有偶数个蓝色节点，将当前节点图成蓝色
        {
            ans[u]=1;
            return sum+1;
        }
        else 	//反之图成红色,即不染色
            return sum;
    }
    dfs(1,0);
    for (let i=1;i<=n;i++)
	{
		if (ans[i]==1)
			process.stdout.write("B");
		else
			process.stdout.write("R");
	}
    
});

题目内容

"小红喜欢蓝色，蓝色是永恒的象征,它是最冷的色彩,表现出一种美丽、文静、理智、安祥与洁净。 由于蓝色沉稳的特性,具有理智,准确的意象"

给你一棵$n$个节点的有根树，编号从 $1$ 到 $n$ ,根是 $1$ 号节点。初始时，树上的每个节点都是红色。现在小红需要你构造一种"子树蓝奇"状态:这棵树的以任意一个节点为根的子树内蓝色节点的个数是奇数个。但这样的方案可太多了，所以小红要求你找到蓝色节点数最多的"子树蓝奇"状态,并输出这棵树。

输入描述

第一行输入一个正整数 $n$ 。

接下来 $n-1$ 行，每行两个正整数 $u,v$ ,表示 $u$ 号节点和 $u$ 号节点之间有一条边。

$1 < n < 10^5$

$1\leq u,v \leq n$

输出描述

输出一个长度为 $n$ 的字符串，表示染色后的树。如果第个字符是'$R$',代表树上的 $i$ 号节点是红色;如果个字符是'$B$',则表示树上的第 $i$ 号节点是蓝色。

样例

输入

6
1 2
1 3
3 4
4 5
5 6

输出

BBRRRB