题解 | #红和蓝#

首先红色和蓝色是轮换对称的，翻转颜色没有问题。

假设我们合法的找到一个答案，一棵树的根节点假设为红色，那么他的儿子节点里一定是有一个红色，其他都是蓝色。蓝色的子树根和父节点没关系了，自身又是一个合法的答案；而红色的那个子树不是，因为他的根是和父节点配对的，但是红色子树的根和他的下面没有关系，因此红色子树的每一个子树又是一个完整的子树。

这样就可以把树分为三类，一类是可以合法染色（记作0），一类是所有子树可以合法染色，但多出来一个根节点被孤立了，给他们上面再加一个点就可以合法染色（记作1）。还有一类则是不能染色（记作-1）。

遍历一个树的每一个子树，如果他的每一个子树都可以返回0，则他自己就是情况1（叶节点没有子树，显然单独一个叶节点也属于情况1）；

如果他的子树中恰好有一个情况1，其余都是情况0，那么根节点自己就跟这个情况1的子树配对，整棵树可以完全染色属于情况0；

如果有多于一个子树出现情况1，则需要每个子树的都取根节点颜色，这个时候根节点连接的同色过多了，属于情况-1；只要有一个子树返回了-1，那么整个树都是无解的，可以直接返回了。

如果最后整棵树是情况0，则找到了解，将自身和自身的配对儿子染红，然后递归染色所有子树为蓝即可。如果最后整棵树是情况1和-1，则没有解

#include <bits/stdc++.h>

constexpr int MAX = 1e5 + 3;
constexpr int root = 1;

int N, chosen[MAX], ans[MAX];
std::vector<int> out[MAX];

int DFS(int u, int fa) {
	for (int v: out[u]) if (v != fa) {
		int t = DFS(v, u);
		if (t == 1) {
			if (chosen[u]) return -1;
			else chosen[u] = v;
		} else if (t == -1) return -1;
	} return chosen[u] ? 0 : 1;
}

void colorize(int u, int fa, int clr) {
	ans[u] = clr;
	if (chosen[u]) {
		ans[chosen[u]] = clr;
		for (int v: out[chosen[u]]) if (v != u)
			colorize(v, chosen[u], clr^1);
	}
	for (int v: out[u]) if (v != fa && v != chosen[u]) {
		colorize(v, u, clr^1);
	}
}

int main() {
	scanf("%d",&N);
	for (int i = 1; i < N; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		out[u].push_back(v);
		out[v].push_back(u);
	}

	if (DFS(root, -1)) puts("-1");
	else {
		colorize(root, -1, 1);
		for (int i = 1; i <= N; ++i) putchar(ans[i] ? 'R':'B');
	}
}