字节笔试10-8

第一题：染色
有一个树，根节点是1，你可以给它染红，蓝，绿三种颜色，但是每一个结点的染色不能和他的父亲结点和爷爷结点颜色相同。第一行输入n，代表n个结点，第二行输入n-1组数，代表n-1条边，左右分别是u,v，u是v的父亲结点。请给出任意一种可行的解。

样例如下，
输入为：
4
1 2
3 4
1 3

输出：
BGRG

一开始楼主也不会，真的放了个国庆直接废了，而且本身基础也不扎实，再加上一下比较慌没看到根节点其实已经给出来了就是1，就没做出来，其实后来静下心来看看是很简单的（心态真的很重要）。

为什么说简单呢？ 第一，他给了我们三种颜色，说子节点不和父亲结点、爷爷结点同色，由于3>2，随便父亲和爷爷结点是什么搭配，你一定至少剩下一种颜色可以选。所以我们从根节点1开始随便选一种颜色，必定可以走到最后，不存在走到半路无解还需要回溯的情况。所以也就不需要什么dfs，回溯法云云。

我是这么想的：建立一个队列用二叉树层序遍历，一开始直接用红色，后续就有哪种用哪种就完了

代码如下：

n = int(input().strip())
g = dict()
for i in range(1,n+1):
    g[i] = []
for _ in range(n-1):
    u,v = list(map(int,input().strip().split()))
    g[u].append(v)
colors = ['R','G','B']
res = ['R']*n
queue = [(1,'R',None)]
while queue:
    node,cur_col,father_col = queue.pop(0)
    for child in g[node]:
        for color in colors:
            if color!=cur_col and color!=father_col:
                res[child-1] = color
                queue.append((child,color,cur_col))
print(res)

queue的每一个结点都记录当前结点编号，当前结点颜色以及父亲结点颜色，那么从queue中pop出来的结点，我们去找他的子节点，然后遍历colors一定能找到一种可用的颜色，再添加到答案中并把孩子结点也塞到queue中，直到层序遍历完，答案也就有了。