问题描述

描述：
你拿到了一棵树，请你给每个顶点染成红色或蓝色。
要求：每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
“周围”的定义：某点周围的点指通过邻边直接连接的点。
所谓树，即没有自环、重边和回路的无向连通图。

输入描述：
第一行一个正整数 n，代表树的顶点个数.。(1≤n≤100000)
接下来的 n-1 行，每行两个正整数 u 和 v，代表点 u 和点 v 有一条边连接。 (1≤u,v≤n)
保证输入的一定是一棵合法的树。

输出描述：
如果可以达成染色的要求，请输出一个长度为 n 的字符串，第 i 个字符代表第 i 个顶点的染色情况，‘B’ 代表蓝色，‘R’ 代表红色。（若有多种合法染色的方法，输出任意一种即可）
否则直接输出-1。

示例1：
输入：

4
1 2
2 3
3 4

输出：

RRBB
说明：
1为红点，它连接的边有只有一个红点：2
2为红点，它连接的边有只有一个红点：1
3为蓝点，它连接的边有只有一个蓝点：4
4为蓝点，它连接的边有只有一个蓝点：3

示例2：
输入：

4
1 2
1 3
1 4

输出：
-1
说明：
可以证明，无论怎么染色，都无法满足题目的要求。

问题分析

①对于叶子节点，周围只有一个点就是它的父亲节点，题目要求每个点周围有且仅有一个红点/蓝点，所以叶子节点的颜色与其父亲节点的颜色一定是相同的；
②如果一个节点有多个叶子节点，那么整颗树是无法染色的，因为如果第一个叶子节点和父节点颜色都是R，根据题目要求第二个叶子节点应该是B，但是这样又不符合我们上面①分析的结果，所以如果一个节点有多个叶子节点，结果一定是 -1；

解题思路

我们使用深度优先搜索【DFS】遍历一次树，标记叶子节点及其父节点同色，将标记的点去掉后就会有新的叶子节点，然后重复这步操作。
- DFS遍历过程中，这个点若是叶子节点，将其与其父节点标记为同色，也就是赋予一个标记；
- 这个点不是叶子节点但未与子树中任何点同色，标记它和它的父亲节点同色；
- 如果同一个点被标记两次，则返回 -1；
- 如果根节点没有被标记，返回 -1；
再进行一次DFS，对节点上色。如果一个点与父亲节点标记相同，则颜色相同，如果标记不同，则颜色相反。

在这里插入图片描述

C代码

#include <stdio.h>
#include <string.h>

int mark = 0;  //标记同色的父子节点
int head[100010]; // 存储树的索引节点
struct ty
{
    int value; // 边的值
    int next;  // 相邻边的索引
}edge[200010];

int dp[100010]={0}; // 第一次DFS时，每个点的标记信息
int color[100010]={0}; // 第二次DFS时，记录每个节点的颜色信息

/* 添加新的边到树型结构中 */
void addedge(int x, int y,int pos)
{
    edge[pos].value = y;
    edge[pos].next = head[x];
    head[x] = pos;
}

int dfs1(int x,int father)
{
    int son=0;
    for(int i=head[x];i != -1;i = edge[i].next)
    {
        if(edge[i].value != father) // 避免回环
        {
            ++son;
            if(dfs1(edge[i].value,x)) return 1; 
        }
    }
    // son==0表示叶子节点 ； dp[x]==0 表示 x 这个点未被标记
    if(son == 0 || dp[x]==0)
    {
        if(dp[father] !=0) return 1; // 一个节点被多次标记，无解
        dp[x] = dp[father] = ++mark;
    }
    return 0;
}

void dfs2(int x,int father)
{
    for(int i=head[x];i != -1;i = edge[i].next)
    {
        if(edge[i].value != father) // 避免回环
        {
            if(dp[edge[i].value] == dp[x])
                color[edge[i].value] = color[x]; // 两个节点标记相同，则颜色相同
            else
                color[edge[i].value] = !color[x]; // 两个节点标记不同，则颜色不同
            dfs2(edge[i].value, x);
        }
    }
}

int main()
{
    int x,y,n,pos=1;
    scanf("%d",&n);
    memset(head, -1, sizeof(head));
    memset(edge, -1, sizeof(edge));
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        addedge(x, y,pos);
        ++pos;
        addedge(y, x,pos);
        ++pos;
    }

	// 1==dfs1(1,0) 表示无解
	// dp[0] 其实是整个树的第一个节点的根节点，上面的code中，我们的树是从pos==1开始的
	// 也就是第一个节点的标记信息在dp[1]中，这里使用dp[0]就是为了观察第一个节点(dp[1])有没有被孤立
	// 如果孤立了则dp[0]一定被标记了，反之dp[0]一定为0
    if(dfs1(1,0) || dp[0])
    {
        printf("-1");
        return 0;
    }
    color[1]=1; // 这里也可以是0，题目也说了可能多解
    dfs2(1,0);
    for(int i=1;i<=n;++i)
    {
        printf("%c",color[i]?'R':'B');
    }
    
    return 0;
}