链接：https://ac.nowcoder.com/acm/contest/9981/C
题目
你拿到了一棵树，请你给每个顶点染成红色或蓝色。 要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。 “周围”的定义：某点周围的点指通过邻边直接连接的点。 所谓树，即没有自环、重边和回路的无向连通图。
输入与输出
输入
第一行一个正整数 n，代表树的顶点个数。(1≤n≤100000)
接下来的 n-1 行，每行两个正整数 u 和 v，代表点 u 和点 v 有一条边连接。(1≤u,v≤n)
保证输入的一定是一棵合法的树。
输出
如果可以达成染色的要求，请输出一个长度为 n 的字符串，第 i 个字符代表第 i 个顶点的染色情况，'B' 代表蓝色，'R' 代表红色。（若有多种合法染色的方法，输出任意一种即可）
否则直接输出-1。
思路
采用染色法,由于是一个树,那么无论从哪一个点开始染色都可以,不妨选择编号为 1 的点,先统计出以 1 号点为根节点的所有点的子树大小
再考虑每一个点 i :
-
如果它与其父亲节点颜色相同,那么它的子树大小必须均为偶数(否则无法满足题意),且与 i 相连的点的颜色和 i 不同
-
如果它与父亲节点颜色不同,那么它的字数大小必须有且只有一个是奇数，其他均为偶数,且为奇数的字数与 i 相连的点的颜色与 i 相同,其它与 i 相连的点 的颜色与 i 不同
不难发现,如果有合法的染色方案,那么一定只有相反的两种方法,所以如果在染色的过程中无法满足题意,那么就一定不存在合法的染色方案了
代码
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e6+7;
int n,head[maxn],cnt,color[maxn],sonNumber[maxn];//sonNumber表示子树大小
bool isFailed = false;//是否染色失败
struct Edge {
int from, to;
}e[maxn<<1];
inline void add(int u, int v)
{
e[++cnt].from = head[u];
e[cnt].to = v;
head[u] = cnt;
}
int calcSon(int nowPoint,int lastPoint)//计算子树大小,lastPoint表示上一个点
{
int sum = 1;
for(int i = head[nowPoint];i;i = e[i].from) {
int nextPoint = e[i].to;
if(nextPoint == lastPoint)
continue;
sum += calcSon(nextPoint, nowPoint);
}
return sonNumber[nowPoint] = sum;
}
void dfs(int nowPoint, int lastPoint, int nowColor)//用0,1表示点的颜色
{
if(isFailed)
return ;
color[nowPoint] = nowColor;
int cnt = 0 ;
for(int i = head[nowPoint]; i; i = e[i].from) {
int nextPoint = e[i].to;
if(nextPoint != lastPoint)
cnt += sonNumber[nextPoint] & 1;//判断它的子节点的树大小是否有且只有一个奇数
}
if(color[nowPoint] == color[lastPoint]) {//情况一
if(cnt) {
isFailed = true;
return ;
}
for(int i = head[nowPoint]; i; i = e[i].from) {
int nextPoint = e[i].to;
if(nextPoint != lastPoint)
dfs(nextPoint, nowPoint, nowColor^1);
}
}
else {//情况二
if(cnt != 1) {
isFailed = true;
return ;
}
for(int i = head[nowPoint]; i ;i = e[i].from) {
int nextPoint = e[i].to;
if(nextPoint != lastPoint) {
if(sonNumber[nextPoint] & 1)//如果是大小为奇数的子树
dfs(nextPoint, nowPoint, nowColor);
else
dfs(nextPoint, nowPoint, nowColor^1);
}
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i < n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
add(x,y); add(y,x);
}
sonNumber[1] = calcSon(1, 0);
dfs(1,0,1);
if(isFailed)
printf("-1\n");
else {
for(int i = 1; i <= n; ++i) {
if (color[i])
printf("B");
else
printf("R");
}
}
return 0;
}
